Fixed-Parameter Tractability of Treewidth and Pathwidth

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

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