Solving problems on graphs of high rank-width

DOI10.1007/S00453-017-0290-8MaRDI QIDQ1709595zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Eduard Eiben, Robert Ganian, Stefan Szeider

Publication date 6 April 2018

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-017-0290-8

zbMATH Keywords

fixed-parameter algorithmsmonadic second-order logicparameterized complexityrank-width

Mathematics Subject Classification ID

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)

Recommendations

• Solving problems on graphs of high rank-width
• Meta-kernelization using Well-structured Modulators
• Meta-kernelization using well-structured modulators
• Meta-kernelization with structural parameters
• Parameterized Algorithms for Modular-Width

Cites work

• scientific article; zbMATH DE number 4204394 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A note on \(\alpha\)-redundant vertices in graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Approximating clique-width and branch-width
• Backdoors into heterogeneous classes of SAT and CSP
• Boundary classes of graphs for the dominating set problem
• Chordal editing is fixed-parameter tractable
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Complement reducible graphs
• Decomposition of Directed Graphs
• Digraph Decompositions and Eulerian Systems
• Distance labeling scheme and split decomposition
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Elements of finite model theory.
• Finding Branch-Decompositions and Rank-Decompositions
• Fundamentals of parameterized complexity
• Independent set in \(P_5\)-free graphs in polynomial time
• Kernel bounds for path and cycle problems
• Kernelization using structural parameters on sparse graph classes
• Linear time solvable optimization problems on graphs of bounded clique-width
• Linear time split decomposition revisited
• Meta-kernelization using Well-structured Modulators
• Meta-kernelization with structural parameters
• On feedback vertex set: new measure and new structures
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Parameterized algorithms
• Parameterized complexity of vertex colouring
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Practical and efficient split decomposition via graph-labelled trees
• Robust algorithms for the stable set problem
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

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
• scientific article; zbMATH DE number 992954 (Why is no real title available?)

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)