Solving problems on graphs of high rank-width
From MaRDI portal
Publication:1709595
DOI10.1007/s00453-017-0290-8zbMath1390.68342OpenAlexW2258298398WikidataQ93047965 ScholiaQ93047965MaRDI QIDQ1709595
Eduard Eiben, Stefan Szeider, Robert Ganian
Publication date: 6 April 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-017-0290-8
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 (2)
Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Chordal editing is fixed-parameter tractable
- Fundamentals of parameterized complexity
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Practical and efficient split decomposition via graph-labelled trees
- On feedback vertex set: new measure and new structures
- Elements of finite model theory.
- Backdoors into heterogeneous classes of SAT and CSP
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Complement reducible graphs
- Robust algorithms for the stable set problem
- Distance labeling scheme and split decomposition
- Parameterized complexity of vertex colouring
- Boundary classes of graphs for the dominating set problem
- 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
- Kernelization Using Structural Parameters on Sparse Graph Classes
- Meta-kernelization with Structural Parameters
- Kernel Bounds for Path and Cycle Problems
- Linear Time Split Decomposition Revisited
- Digraph Decompositions and Eulerian Systems
- Decomposition of Directed Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Meta-kernelization using Well-structured Modulators
- Independent Set in P5-Free Graphs in Polynomial Time
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Parameterized Algorithms
- Finding Branch-Decompositions and Rank-Decompositions
- A note on \(\alpha\)-redundant vertices in graphs
This page was built for publication: Solving problems on graphs of high rank-width
