Cut and count and representative sets on branch decompositions

DOI10.4230/LIPICS.IPEC.2016.27MaRDI QIDQ4634412zbMATH OpenOpenAlexFDO

Authors Willem J. A. Pino, Johan M. M. Van Rooij, Hans L. Bodlaender

Publication date 10 April 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.IPEC.2016.27

zbMATH Keywords

dynamic programmingtreewidthgraph algorithmsplanar graphsbranchwidth

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Dynamic programming (90C39)

Recommendations

• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Faster algorithms on branch and clique decompositions
• STACS 2004
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

Cited in

(11)

• Dynamic programming for graphs on surfaces
• Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
• Dynamic programming for graphs on surfaces
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Fast Algorithms for Join Operations on Tree Decompositions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• On the exact complexity of Hamiltonian Cycle and \(q\)-Colouring in disk graphs
• Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
• Speeding up dynamic programming with representative sets. An experimental evaluation of algorithms for Steiner Tree on tree decompositions
• Tight Bounds for Gomory-Hu-like Cut Counting
• Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space

This page was built for publication: Cut and count and representative sets on branch decompositions

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