Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth

DOI10.1007/978-3-031-43380-1_28MaRDI QIDQ6496555zbMATH OpenFDO

Authors Falko Hegerfeld, Stefan Kratsch

Publication date 3 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-43380-1_28

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A survey of the algorithmic aspects of modular decomposition
• Cut and count and representative sets on branch decompositions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Finer tight bounds for coloring on clique-width
• Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• scientific article; zbMATH DE number 7650914 (Why is no real title available?)
• Known algorithms on graphs of bounded treewidth are probably optimal
• Matching is as easy as matrix inversion
• Model counting for CNF formulas of bounded modular treewidth
• More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
• On the Relationship Between Clique-Width and Treewidth
• Parameterized compilation lower bounds for restricted CNF-formulas
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Transitiv orientierbare Graphen
• Treewidth. Computations and approximations

Cited in

(4)

• A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
• Bridging treewidth and clique-width via cograph-modular-treewidth
• Tight bounds for connected odd cycle transversal parameterized by clique-width
• The parameter report: an orientation guide for data-driven parameterization

This page was built for publication: Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6496555)