Cut and count and representative sets on branch decompositions

DOI10.4230/LIPICS.IPEC.2016.27zbMATH Open1398.05205OpenAlexW2514415970MaRDI QIDQ4634412FDOQ4634412

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

Publication date: 10 April 2018

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

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

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)

Cited In (5)

• On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
• Fast Algorithms for Join Operations on Tree Decompositions
• Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
• Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
• Tight Bounds for Gomory-Hu-like Cut Counting

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)