Solving problems on graphs of high rank-width
DOI10.1007/S00453-017-0290-8zbMATH Open1390.68342DBLPjournals/algorithmica/EibenGS18OpenAlexW2258298398WikidataQ93047965 ScholiaQ93047965MaRDI QIDQ1709595FDOQ1709595
Authors: Eduard Eiben, Robert Ganian, Stefan Szeider 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Decidability of theories and sets of sentences (03B25)
Cites Work
- Fundamentals of parameterized complexity
- Complement reducible graphs
- Boundary classes of graphs for the dominating set problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- Approximating clique-width and branch-width
- Title not available (Why is that?)
- Independent set in \(P_5\)-free graphs in polynomial time
- Parameterized algorithms
- Title not available (Why is that?)
- Elements of finite model theory.
- Backdoors into heterogeneous classes of SAT and CSP
- Digraph Decompositions and Eulerian Systems
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Algorithmic Aspects of Vertex Elimination on Graphs
- Parameterized complexity of vertex colouring
- Kernelization using structural parameters on sparse graph classes
- Linear time split decomposition revisited
- Chordal editing is fixed-parameter tractable
- Decomposition of Directed Graphs
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- A note on \(\alpha\)-redundant vertices in graphs
- Kernel bounds for path and cycle problems
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- Finding Branch-Decompositions and Rank-Decompositions
- Title not available (Why is that?)
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Distance labeling scheme and split decomposition
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Practical and efficient split decomposition via graph-labelled trees
- On feedback vertex set: new measure and new structures
- Meta-kernelization with structural parameters
- Meta-kernelization using Well-structured Modulators
- Robust algorithms for the stable set problem
- Closing complexity gaps for coloring problems on \(H\)-free graphs
Cited In (5)
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Solving problems on graphs of high rank-width
- On \textsf{NC} algorithms for problems on bounded rank-width graphs
- Title not available (Why is that?)
This page was built for publication: Solving problems on graphs of high rank-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709595)
