Solving Problems on Graphs of High Rank-Width

DOI10.1007/978-3-319-21840-3_26zbMath1392.68199arXiv1507.05463OpenAlexW2618339652MaRDI QIDQ3449829

Eduard Eiben, Robert Ganian, Stefan Szeider

Publication date: 30 October 2015

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

Full work available at URL: https://arxiv.org/abs/1507.05463

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Decidability of theories and sets of sentences (03B25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, Meta-kernelization using well-structured modulators, Backdoor Sets for CSP., On structural parameterizations of the bounded-degree vertex deletion problem, Backdoors into heterogeneous classes of SAT and CSP

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Kernel bounds for path and cycle problems
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Practical and efficient split decomposition via graph-labelled trees
• Elements of finite model theory.
• Backdoors into heterogeneous classes of SAT and CSP
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Robust algorithms for the stable set problem
• Parameterized complexity of vertex colouring
• Linear time solvable optimization problems on graphs of bounded clique-width
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Approximating clique-width and branch-width
• A theory of regular MSC languages
• Kernelization Using Structural Parameters on Sparse Graph Classes
• Decomposition of Directed Graphs
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Independent Set in P₅-Free Graphs in Polynomial Time
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Finding Branch-Decompositions and Rank-Decompositions
• A note on \(\alpha\)-redundant vertices in graphs