The rank-width of the square grid

DOI10.1016/J.DAM.2009.02.007zbMATH Open1219.05153OpenAlexW2142161693MaRDI QIDQ972345FDOQ972345

Vít Jelínek

Publication date: 25 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.02.007

Recommendations

• The Rank-Width of the Square Grid
• Rank‐width is less than or equal to branch‐width
• Rank-width and vertex-minors
• Rank-width: algorithmic and structural results
• Rank-width of random graphs

zbMATH Keywords

graph decompositionrank-widthgrid graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Cites Work

• Approximating clique-width and branch-width
• Rank‐width is less than or equal to branch‐width
• Finding Branch-Decompositions and Rank-Decompositions

Cited In (13)

• Digraphs of Bounded Width
• The carving-width of generalized hypercubes
• Branch decomposition heuristics for linear matroids
• Bounds for the Twin-Width of Graphs
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Bipartite entanglement in continuous variable cluster states
• Clique-width and edge contraction
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Graph Classes with Structured Neighborhoods and Algorithmic Applications
• Rank-width: algorithmic and structural results
• Characterizing graphs of maximum matching width at most 2
• Thinness and its variations on some graph families and coloring graphs of bounded thinness
• The Rank-Width of the Square Grid

This page was built for publication: The rank-width of the square grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972345)