Fixed-Parameter Tractability of Treewidth and Pathwidth (Q2908539): Difference between revisions

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