Solving Problems on Graphs of High Rank-Width
From MaRDI portal
Publication:3449829
DOI10.1007/978-3-319-21840-3_26zbMath1392.68199arXiv1507.05463MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C75: Structural characterization of families of graphs
03B25: Decidability of theories and sets of sentences
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Backdoor Sets for CSP., Backdoors into heterogeneous classes of SAT and CSP, 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, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
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 P5-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