Fixed-Parameter Tractability of Treewidth and Pathwidth

DOI10.1007/978-3-642-30891-8_12zbMath1358.68119OpenAlexW135876007WikidataQ56679465 ScholiaQ56679465MaRDI QIDQ2908539

Hans L. Bodlaender

Publication date: 5 September 2012

Published in: The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-30891-8_12

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A Basic Parameterized Complexity Primer, Approximating Pathwidth for Graphs of Small Treewidth, The complexity of minimum-length path decompositions, Unnamed Item, Width, depth, and space: tradeoffs between branching and dynamic programming, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, On the treewidth of Hanoi graphs

Uses Software

• ComputeTW

Cites Work

• Courcelle's theorem -- a game-theoretic approach
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
• Treewidth computations. II. Lower bounds
• On the complexity of some colorful problems parameterized by treewidth
• The complexity of subgraph isomorphism for classes of partial k-trees
• Monadic second-order evaluations on tree-decomposable graphs
• Graph minors. XX: Wagner's conjecture
• Graph minors. III. Planar tree-width
• Approximation algorithms for treewidth
• Safe reduction rules for weighted treewidth
• Treewidth computations. I: Upper bounds
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Dynamic programming and planarity: improved tree-decomposition based algorithms
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• Derivation of algorithms for cutwidth and related graph layout parameters
• On two techniques of combining branching and treewidth
• Graph minors. XXI. graphs with unique linkages
• On problems without polynomial kernels
• Graph minors. I. Excluding a forest
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. VI. Disjoint paths across a disc
• Graph minors. V. Excluding a planar graph
• Nonconstructive advances in polynomial-time complexity
• Graph minors. VII: Disjoint paths on a surface
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Black-white pebbles and graph separation
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Graph minors. X: Obstructions to tree-decomposition
• Quickly excluding a forest
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• The vertex separation number of a graph equals its path-width
• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• A partial k-arboretum of graphs with bounded treewidth
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Highly connected sets and the excluded grid theorem
• Graph minors. XI: Circuits on a surface
• Call routing and the ratcatcher
• The vertex separation and search number of a graph
• Improved self-reduction algorithms for graphs with bounded treewidth
• Quickly excluding a planar graph
• Treewidth. Computations and approximations
• On search, decision, and the efficiency of polynomial-time algorithms
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
• Channel assignment on graphs of bounded treewidth
• Graph minors. XIX: Well-quasi-ordering on a surface.
• Graph minors. XVII: Taming a vortex
• Algorithms for generalized vertex-rankings of partial k-trees
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• On computing graph minor obstruction sets
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• A linear algorithm for finding \([g,f\)-colorings of partial \(k\)-trees]
• Dynamic algorithms for graphs of bounded treewidth
• Definability equals recognizability of partial 3-trees and \(k\)-connected partial \(k\)-trees
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• A comparison of structural CSP decomposition methods
• Counting \(H-\)colorings of partial \(k-\)trees
• Listing all potential maximal cliques of a graph
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Graph minors. IX: Disjoint crossed paths
• Reduction algorithms for graphs of small treewidth
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XII: Distance on a surface
• Graph minors. XIV: Extending an embedding
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Graph minors. XV: Giant steps
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Linear time solvable optimization problems on graphs of bounded clique-width
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Algorithms finding tree-decompositions of graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• New upper bounds on the decomposability of planar graphs
• New Limits to Classical and Quantum Instance Compression
• Faster Algorithms on Branch and Clique Decompositions
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Nonconstructive tools for proving polynomial-time decidability
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Resilience of partialk-tree networks with edge and node failures
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Polynomial-time self-reducibility: theoretical motivations and practical results^∗
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• An algebraic theory of graph reduction
• Parametric Problems on Graphs of Bounded Tree-Width
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Recognizability equals definability for partial k-paths
• The Pathwidth and Treewidth of Cographs
• Linear-time computation of optimal subgraphs of decomposable graphs
• Solving partial constraint satisfaction problems with tree decomposition
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• On Linear Recognition of Tree-Width at Most Four
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• On Moderately Exponential Time for SAT
• (Meta) Kernelization
• A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
• A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES
• Bidimensionality and Geometric Graphs
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item