Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
From MaRDI portal
Publication:967316
DOI10.1016/j.dam.2008.08.023zbMath1211.05065OpenAlexW2003591274MaRDI QIDQ967316
Publication date: 28 April 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.023
dynamic programmingtreewidthpath-decompositiondominating settree-decompositionbranch-decompositionbrachwidth
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)
Related Items
The graphs of stably matchable pairs, Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs, A Local Search Algorithm for Branchwidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(K_{1,3}\)-free and \(W_4\)-free graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Graph minors. X: Obstructions to tree-decomposition
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Tour Merging via Branch-Decomposition
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- STACS 2004
- Automata, Languages and Programming
- Algorithms – ESA 2005