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)
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
- 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
