Graph minors. X: Obstructions to tree-decomposition
From MaRDI portal
Publication:1179473
DOI10.1016/0095-8956(91)90061-NzbMath0764.05069WikidataQ56001805 ScholiaQ56001805MaRDI QIDQ1179473
Publication date: 26 June 1992
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
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 (only showing first 100 items - show all)
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 ⋮ 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)
Cites Work
- Unnamed Item
- Graph minors. V. Excluding a planar graph
- Quickly excluding a planar graph
- Graph minors. XVI: Excluding a non-planar graph
- Graph minors. XII: Distance on a surface
- Graph minors. IV: Tree-width and well-quasi-ordering
- Graph minors. VIII: A Kuratowski theorem for general surfaces
- In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
This page was built for publication: Graph minors. X: Obstructions to tree-decomposition
