Fixed-Parameter Tractability of Treewidth and Pathwidth
From MaRDI portal
Publication:2908539
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
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
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