Computing rank-width exactly

DOI10.1016/j.ipl.2009.03.018zbMath1197.05151OpenAlexW2113302924MaRDI QIDQ989474

Sang-il Oum

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.03.018

zbMATH Keywords

graph algorithmsexact exponential algorithmsrank-widthbranch-widthfast subset convolution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Rank-width: algorithmic and structural results ⋮ Tangle bases: Revisited ⋮ Bipartite entanglement in continuous variable cluster states ⋮ The carving-width of generalized hypercubes

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Approximating clique-width and branch-width
• Fast multiplication of large numbers
• Fourier meets M\"{o}bius: fast subset convolution
• Graph Drawing
• Graph-Theoretic Concepts in Computer Science
• Finding Branch-Decompositions and Rank-Decompositions