The rank-width of the square grid

DOI10.1016/j.dam.2009.02.007zbMath1219.05153OpenAlexW2142161693MaRDI QIDQ972345

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

zbMATH Keywords

graph decompositiongrid graphrank-width

Mathematics Subject Classification ID

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

Related Items (11)

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

Cites Work

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

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