Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm

DOI10.1016/j.dam.2008.08.023zbMath1211.05065OpenAlexW2003591274MaRDI QIDQ967316

Jan Arne Telle, Frederic Dorn

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

zbMATH Keywords

dynamic programmingtreewidthpath-decompositiondominating settree-decompositionbranch-decompositionbrachwidth

Mathematics Subject Classification ID

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