Better polynomial algorithms on graphs of bounded rank-width

DOI10.1007/978-3-642-10217-2_27MaRDI QIDQ3651552zbMATH OpenOpenAlexFDO

Authors Robert Ganian, Petr Hliněný

Publication date 11 December 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-10217-2_27

zbMATH Keywords

chromatic numberchromatic polynomialHamiltonian pathpseudopolynomial algorithmsrank-decompositionrank-width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• Graph-Theoretic Concepts in Computer Science
• Approximating rank-width and clique-width quickly
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Thread graphs, linear rank-width and their algorithmic applications

Cited in

(12)

• On \textsf{NC} algorithms for problems on bounded rank-width graphs
• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Obstructions for linear rank-width at most 1
• Thread graphs, linear rank-width and their algorithmic applications
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• On digraph width measures in parameterized algorithmics
• scientific article; zbMATH DE number 6850484 (Why is no real title available?)
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• Graph-Theoretic Concepts in Computer Science
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

This page was built for publication: Better polynomial algorithms on graphs of bounded rank-width

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