Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth

DOI10.1007/978-3-031-43380-1_28MaRDI QIDQ6496555

Falko Hegerfeld, Stefan Kratsch

Publication date: 3 May 2024

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Model counting for CNF formulas of bounded modular treewidth
• A survey of the algorithmic aspects of modular decomposition
• Matching is as easy as matrix inversion
• Treewidth. Computations and approximations
• Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Parameterized Compilation Lower Bounds for Restricted CNF-Formulas
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
• Cut and Count and representative sets on branch decompositions
• More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
• Finer Tight Bounds for Coloring on Clique-Width
• On the Relationship Between Clique-Width and Treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Transitiv orientierbare Graphen

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