Graph minors. X: Obstructions to tree-decomposition

From MaRDI portal

Publication:1179473

Jump to:navigation, search

DOI10.1016/0095-8956(91)90061-NzbMath0764.05069WikidataQ56001805 ScholiaQ56001805MaRDI QIDQ1179473

P. D. Seymour, Neil Robertson

Publication date: 26 June 1992

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

hypergraphs separation minors tangle tree-width tree-decomposition

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Duality Theorems for Blocks and Tangles in Graphs, Refining a Tree-Decomposition which Distinguishes Tangles, A tight relation between series-parallel graphs and bipartite distance hereditary graphs, A canonical tree-of-tangles theorem for structurally submodular separation systems, A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface, Matroids Representable Over Fields With a Common Subfield, Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms, Constructing Brambles, Subexponential Fixed-Parameter Algorithms for Partial Vector Domination, Unnamed Item, Constructive linear time algorithms for branchwidth, Finding branch-decompositions of matroids, hypergraphs, and more, Connecting Width and Structure in Knowledge Compilation (Extended Version), Trees of tangles in infinite separation systems, Algorithms for Propositional Model Counting, Packing cycles in undirected group-labelled graphs, Unnamed Item, Spined categories: generalizing tree-width beyond graphs, Bounding the mim‐width of hereditary graph classes, Duality theorems for stars and combs IV: Undominating stars, Duality theorems for stars and combs I: Arbitrary stars and combs, Upward book embeddability of \(st\)-graphs: complexity and algorithms, Monoidal Width, Generating random instances of weighted model counting. An empirical analysis with varying primal treewidth, Graph coloring with no large monochromatic components, Tangle bases: Revisited, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, Branchwidth is \((1, g)\)-self-dual, Bounding branch-width, Packing topological minors half‐integrally, Monotonicity of Non-deterministic Graph Searching, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Entanglements, Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree, Monoidal Width: Capturing Rank Width, A Branch Decomposition Algorithm for the p-Median Problem, Tree automata and pigeonhole classes of matroids. II, Tangles and Hierarchical Clustering, Pathwidth vs Cocircumference, A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups, Classes of intersection digraphs with good algorithmic properties, Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds, Computing Minimum k-Connected m-Fold Dominating Set in General Graphs, On the Block Number of Graphs, Solving problems on generalized convex graphs via mim-width, On the Optimality of Pseudo-polynomial Algorithms for Integer Programming, Partitioning \(H\)-minor free graphs into three subgraphs with no large components, Bounding the Mim-Width of Hereditary Graph Classes., Obstructions for Bounded Branch-depth in Matroids, On the $AC^0$ Complexity of Subgraph Isomorphism, Unnamed Item, Unnamed Item, Unnamed Item, A Short Derivation of the Structure Theorem for Graphs with Excluded Topological Minors, On the number of labeled graphs of bounded treewidth, Unnamed Item, Excluding a bipartite circle graph from line graphs, Parameterized complexity of graph planarity with restricted cyclic orders, Computing with Tangles, The Parameterized Complexity of Graph Cyclability, Graph minor theory, Unnamed Item, Directed Path-Decompositions, Upward Book Embeddings of st-Graphs, Graph Classes with Structured Neighborhoods and Algorithmic Applications, Erdös--Pósa Property for Labeled Minors: 2-Connected Minors, Boolean-Width of Graphs, On Digraph Width Measures in Parameterized Algorithmics, Dynamic programming for graphs on surfaces, Near Isometric Terminal Embeddings for Doubling Metrics, Digraphs of Bounded Width, Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints, Unnamed Item, Finding Branch-Decompositions of Matroids, Hypergraphs, and More, Unnamed Item, Unnamed Item, Node multiway cut and subset feedback vertex set on graphs of bounded mim-width, Edge-maximal graphs of branchwidth k, Canonisation and Definability for Graphs of Bounded Rank Width, Trees, grids, and MSO decidability: from graphs to matroids, Call routing and the ratcatcher, On the contractibility of a digraph onto \(K_ 4^*\), Improved self-reduction algorithms for graphs with bounded treewidth, Solving problems on generalized convex graphs via mim-width, (Total) vector domination for graphs with bounded branchwidth, An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs, Between treewidth and clique-width, Excluding subdivisions of bounded degree graphs, Approximate tree decompositions of planar graphs in linear time, Grids and their minors, On well quasiordering of finite languages, Matroid tree-width, New analysis and computational study for the planar connected dominating set problem, On embedding graphs in trees, Model counting for CNF formulas of bounded modular treewidth, Vertex-minors, monadic second-order logic, and a conjecture by Seese, Online promise problems with online width metrics, Canonical tree-decompositions of a graph that display its \(k\)-blocks, Rooted grid minors, Irrelevant vertices for the planar disjoint paths problem, The subgraph homeomorphism problem for small wheels, Testing branch-width, Some recent progress and applications in graph minor theory, The parameterized complexity of local search for TSP, more refined, Graph classes with structured neighborhoods and algorithmic applications, Connectivity and tree structure in finite graphs, Ends and tangles, Untangling planar curves, Grid minors in damaged grids, Canonical tree-decompositions of finite graphs. I: Existence and algorithms., Are there any good digraph width measures?, Meta-kernelization with structural parameters, Practical algorithms for branch-decompositions of planar graphs, On self-duality of branchwidth in graphs of bounded genus, Graph minors. XXII. Irrelevant vertices in linkage problems, Tree-representation of set families and applications to combinatorial decompositions, On the excluded minors for the matroids of branch-width \(k\), A note on planar graphs with large width parameters and small grid-minors, A combinatorial optimization algorithm for solving the branchwidth problem, Constant-degree graph expansions that preserve treewidth, Satisfiability, branch-width and Tseitin tautologies, On the monotonicity of games generated by symmetric submodular functions., Graph minors. XVI: Excluding a non-planar graph, Graph minors. XVIII: Tree-decompositions and well-quasi-ordering, Local search: is brute-force avoidable?, Clique-width of countable graphs: A compactness property., Subexponential parameterized algorithms, Linear connectivity forces large complete bipartite minors: an alternative approach, Graph minors. XIX: Well-quasi-ordering on a surface., Confronting intractability via parameters, Packing cycles with modularity constraints, Treewidth lower bounds with brambles, Practical algorithms for MSO model-checking on tree-decomposable graphs, Monotonicity of non-deterministic graph searching, An annotated bibliography on guaranteed graph searching, On triangulating \(k\)-outerplanar graphs, Forbidden minors for graphs with no first obstruction to parametric Feynman integration, Quickly excluding a forest, Minimal cutwidth linear arrangements of abelian Cayley graphs, A simple linear-time algorithm for finding path-decompositions of small width, The vertex separation number of a graph equals its path-width, Connected graph searching, Graph minors XXIII. Nash-Williams' immersion conjecture, Partitions versus sets: a case of duality, Branchwidth of chordal graphs, Computing branchwidth via efficient triangulations and blocks, Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm, Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms, Dynamic programming and planarity: improved tree-decomposition based algorithms, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Complexity and approximation of the constrained forest problem, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Graph minors. XX: Wagner's conjecture, The carving-width of generalized hypercubes, Boolean-width of graphs, Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs, Computing rank-width exactly, Connectivity functions and polymatroids, A short proof that every finite graph has a tree-decomposition displaying its tangles, Tangles, trees, and flowers, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, Addendum to matroid tree-width, Edge-maximal graphs of branchwidth \(k\): The \(k\)-branches, Nondeterministic graph searching: from pathwidth to treewidth, Linear connectivity forces large complete bipartite minors, Graph minors. XXI. graphs with unique linkages, Tangles, tree-decompositions and grids in matroids, Edge searching weighted graphs, A partial k-arboretum of graphs with bounded treewidth, Graph operations characterizing rank-width, Graph minors. XVII: Taming a vortex, Computational study on planar dominating set problem, Connecting knowledge compilation classes and width parameters, Separations of sets, Tree-length equals branch-length, Submodular partition functions, Highly connected sets and the excluded grid theorem, Canonical tree-decompositions of finite graphs. II. Essential parts, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Fork-decompositions of matroids, FPT algorithms to enumerate and count acyclic and totally cyclic orientations, An analysis of the parameterized complexity of periodic timetabling, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, Tensor networks and the enumerative geometry of graphs, Biased graphs. VII: Contrabalance and antivoltages, The branchwidth of graphs and their cycle matroids, The relative clique-width of a graph, Vertex partitioning problems on graphs with bounded tree width, Minors in graphs of large \(\theta_r\)-girth, Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree, On objects dual to tree-cut decompositions, Rank-width: algorithmic and structural results, Representations of infinite tree sets, Canonical trees of tree-decompositions, Near isometric terminal embeddings for doubling metrics, A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three, Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract), Between Treewidth and Clique-Width, Abstract separation systems, 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs, Characterizing graphs of maximum matching width at most 2, Maximum matching width: new characterizations and a fast algorithm for dominating set, Profinite separation systems, Approximate search strategies for weighted trees, Local 2-separators, On the excluded minor structure theorem for graphs of large tree-width, Improved bounds on the planar branchwidth with respect to the largest grid minor size, On the optimality of pseudo-polynomial algorithms for integer programming, Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices, Packing \(A\)-paths of length zero modulo a prime, Graph theory. Abstracts from the workshop held January 2--8, 2022, On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs, Parameterized complexity of graph planarity with restricted cyclic orders, The theory of guaranteed search on graphs, Parameters Tied to Treewidth, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, Square roots of minor closed graph classes, Digraph width measures in parameterized algorithmics, Tangle and Maximal Ideal, Branch decomposition heuristics for linear matroids, Tangle-tree duality in abstract separation systems, Faster algorithms for vertex partitioning problems parameterized by clique-width, Tangles and the Stone-Čech compactification of infinite graphs, Branch-depth: generalizing tree-depth of graphs, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, Vertex-minor reductions can simulate edge contractions, Trees of tangles in abstract separation systems, On the hyperbolicity constant in graph minors, Computational study on a PTAS for planar dominating set problem, Hypertree width and related hypergraph invariants, Packing \(A\)-paths of length zero modulo four, Packing and covering immersions in 4-edge-connected graphs, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, Subexponential fixed-parameter algorithms for partial vector domination, Parameterized complexity of the spanning tree congestion problem, Kernels in planar digraphs, Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs, Computing the branchwidth of interval graphs, Strong branchwidth and local transversals, Unnamed Item, Unnamed Item, Branch-width, parse trees, and monadic second-order logic for matroids., On the interval completion of chordal graphs, Algorithms for propositional model counting, Approximating clique-width and branch-width, Obstructions to branch-decomposition of matroids, Turing kernelization for finding long paths in graph classes excluding a topological minor, Contraction obstructions for treewidth, Complexity Results for the Spanning Tree Congestion Problem, On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph, Are There Any Good Digraph Width Measures?, Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs, Obstructions for bounded shrub-depth and rank-depth, The role of planarity in connectivity problems parameterized by treewidth, Measuring what matters: a hybrid approach to dynamic programming with treewidth, C-planarity testing of embedded clustered graphs with bounded dual carving-width, Effects of vertex degrees on the zero-forcing number and propagation time of a graph, A Local Search Algorithm for Branchwidth, Excluding a group-labelled graph, Bounds on vertex colorings with restrictions on the union of color classes, On the domination search number, A SAT Approach to Branchwidth, Linear Time Algorithms for Happy Vertex Coloring Problems for Trees, Tangle and ultrafilter: game theoretical interpretation, Treewidth of graphs with balanced separations, Structural submodularity and tangles in abstract separation systems, On planar graphs with large tree-width and small grid minors, Rank-width and vertex-minors, Unifying the representation of symmetric crossing families and weakly partitive families, Branch-width and well-quasi-ordering in matroids and graphs., On matroids of branch-width three., Matroid 3-connectivity and branch width, Rank connectivity and pivot-minors of graphs, Matroids denser than a clique, A tree-of-tangles theorem for infinite tangles, THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS, ProCount: weighted projected model counting with graded project-join trees

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1179473&oldid=12031203"