Graph minors. II. Algorithmic aspects of tree-width
From MaRDI portal
Publication:3751592
DOI10.1016/0196-6774(86)90023-4zbMath0611.05017OpenAlexW2029448190MaRDI QIDQ3751592
Publication date: 1986
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(86)90023-4
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items (only showing first 100 items - show all)
Disconnected matchings ⋮ Clustered 3-colouring graphs of bounded degree ⋮ Bounding the search number of graph products ⋮ On the pathwidth of hyperbolic 3-manifolds ⋮ Computing Bond Types in Molecule Graphs ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates ⋮ Principled deep neural network training through linear programming ⋮ Spined categories: generalizing tree-width beyond graphs ⋮ The firebreak problem ⋮ Treelength of series-parallel graphs ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ Monoidal Width ⋮ On the complexity of the storyplan problem ⋮ The complexity of learning minor closed graph classes ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ Optimal parallel shortest paths in small treewidth digraphs ⋮ Public goods games in directed networks ⋮ Augmenting graphs to minimize the radius ⋮ Graphs of linear growth have bounded treewidth ⋮ On Interval Routing Schemes and treewidth ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ On the complexity of the storyplan problem ⋮ Dynamic algorithms for graphs with treewidth 2 ⋮ Excluding a planar matching minor in bipartite graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ Monoidal Width: Capturing Rank Width ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Weighted connected matchings ⋮ Unnamed Item ⋮ On the parameterized complexity of s-club cluster deletion problems ⋮ On the parameterized complexity of \(s\)-club cluster deletion problems ⋮ Efficient interprocedural data-flow analysis using treedepth and treewidth ⋮ General space-time tradeoffs via relational queries ⋮ Recognizing map graphs of bounded treewidth ⋮ On integer linear programs for treewidth based on perfect elimination orderings ⋮ Treewidth of the \(q\)-Kneser graphs ⋮ A lower bound for treewidth and its consequences ⋮ Tree-width and path-width of comparability graphs of interval orders ⋮ Bounded tree-width and LOGCFL ⋮ On reduction algorithms for graphs with small treewidth ⋮ Reduction algorithms for constructing solutions in graphs with small treewidth ⋮ Locating Eigenvalues of Symmetric Matrices - A Survey ⋮ Induced subgraphs and tree decompositions V. one neighbor in a hole ⋮ Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs ⋮ An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth ⋮ Eulerian Spaces ⋮ NC-algorithms for graphs with small treewidth ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Unnamed Item ⋮ Minimum size tree-decompositions ⋮ Locating Facilities on a Network to Minimize Their Average Service Radius ⋮ Minimum size tree-decompositions ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ An algorithm for simultaneous backbone threading and side-chain packing ⋮ The complexity of broadcasting in planar and decomposable graphs ⋮ A Practical Approach to Courcelle's Theorem ⋮ The pagenumber of \(k\)-trees is \(O(k)\) ⋮ To Approximate Treewidth, Use Treelength! ⋮ Approximation algorithms for maximum two-dimensional pattern matching ⋮ Power indices and easier hard problems ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ Finding cut-vertices in the square roots of a graph ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Clique-width of point configurations ⋮ Recognizing \(k\)-clique extendible orderings ⋮ Clique-perfectness of complements of line graphs ⋮ Heuristic and metaheuristic methods for computing graph treewidth ⋮ Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited ⋮ Disconnected matchings ⋮ On the treewidth of random geometric graphs and percolated grids ⋮ AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH ⋮ FINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Tree decompositions and social graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Defective Coloring on Classes of Perfect Graphs ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth ⋮ On Treewidth and Related Parameters of Random Geometric Graphs ⋮ Perfect edge domination and efficient edge domination in graphs ⋮ Algorithms for vertex-partitioning problems on graphs with fixed clique-width. ⋮ Graph minors. V. Excluding a planar graph ⋮ A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ The nonexistence of reduction rules giving an embedding into a \(k\)-tree ⋮ \(k\)-NLC graphs and polynomial algorithms ⋮ Eigenvalue location in graphs of small clique-width ⋮ Obstructions to a small hyperbolicity in Helly graphs ⋮ Induced and weak induced arboricities ⋮ Fork-decompositions of matroids ⋮ A polynomial time algorithm for strong edge coloring of partial \(k\)-trees ⋮ Rooted routing in the plane ⋮ Grids and their minors
This page was built for publication: Graph minors. II. Algorithmic aspects of tree-width
