Graph minors. II. Algorithmic aspects of tree-width
From MaRDI portal
Publication:3751592
DOI10.1016/0196-6774(86)90023-4zbMATH Open0611.05017OpenAlexW2029448190MaRDI QIDQ3751592FDOQ3751592
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
Recommendations
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)
Cited In (only showing first 100 items - show all)
- Non-deterministic graph searching in trees
- Community Structure Inspired Algorithms for SAT and #SAT
- APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM
- An exact method for graph coloring
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- Treewidth governs the complexity of target set selection
- Title not available (Why is that?)
- On computational complexity of graph inference from counting
- Structural tractability of counting of solutions to conjunctive queries
- On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity
- Tractable counting of the answers to conjunctive queries
- Courcelle's theorem -- a game-theoretic approach
- The disjoint paths problem in quadratic time
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- A hybrid tractable class for non-binary CSPs
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- Dynamic Management of Heuristics for Solving Structured CSPs
- Treewidth computation and extremal combinatorics
- Recent developments on graphs of bounded clique-width
- Hypertree decompositions and tractable queries
- Graph searching and a min-max theorem for tree-width
- A coloring problem for weighted graphs
- Approximation algorithms for treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Fifty years of the spectrum problem: survey and new results
- Treewidth for graphs with small chordality
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Approximating the pathwidth of outerplanar graphs
- Contraction obstructions for connected graph searching
- Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
- Minimal triangulations of graphs: a survey
- Practical algorithms on partial k-trees with an application to domination-like problems
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Title not available (Why is that?)
- Title not available (Why is that?)
- Recognizability equals definability for partial k-paths
- Inference and learning in probabilistic logic programs using weighted Boolean formulas
- Approximate tree decompositions of planar graphs in linear time
- Branch-width and Rota's conjecture
- On bounded-degree vertex deletion parameterized by treewidth
- A comparison of structural CSP decomposition methods
- Title not available (Why is that?)
- On some optimization problems on \(k\)-trees and partial \(k\)-trees
- Approximation algorithms for maximum two-dimensional pattern matching
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- To Approximate Treewidth, Use Treelength!
- Monotonicity of non-deterministic graph searching
- Surfaces, tree-width, clique-minors, and partitions
- Rank-width and tree-width of \(H\)-minor-free graphs
- Transforming graph states using single-qubit operations
- Monotony properties of connected visible graph searching
- Graph minors. I. Excluding a forest
- Graph minors. III. Planar tree-width
- Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks
- AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
- New analysis and computational study for the planar connected dominating set problem
- The inverse 1-maxian problem with edge length modification
- Treewidth computations. I: Upper bounds
- Forests, colorings and acyclic orientations of the square lattice
- On the pathwidth of chordal graphs
- Splitting a graph into disjoint induced paths or cycles.
- Title not available (Why is that?)
- Algebraic approach to fasciagraphs and rotagraphs
- Digraph width measures in parameterized algorithmics
- Tree-depth, subgraph coloring and homomorphism bounds
- On zeros of the characteristic polynomial of matroids of bounded tree-width
- The pathwidth and treewidth of cographs
- Listing all potential maximal cliques of a graph
- The relative clique-width of a graph
- Spanners for bounded tree-length graphs
- Computational properties of argument systems satisfying graph-theoretic constraints
- Computational study on planar dominating set problem
- Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
- Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts
- Are There Any Good Digraph Width Measures?
- Graphs of small rank-width are pivot-minors of graphs of small tree-width
- Representing graphs as the intersection of cographs and threshold graphs
- Perfect edge domination and efficient edge domination in graphs
- A spectral lower bound for the treewidth of a graph and its consequences
- The Potts model and the Tutte polynomial.
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- A logical approach to multicut problems
- Pathwidth of cubic graphs and exact algorithms
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Dynamic algorithms for graphs of bounded treewidth
- The critical node detection problem in networks: a survey
- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
- Title not available (Why is that?)
- Acyclic coloring parameterized by directed clique-width
- Contraction bidimensionality of geometric intersection graphs
- Are there any good digraph width measures?
- Title not available (Why is that?)
- On the complexity of constrained Nash equilibria in graphical games
- Collective tree spanners in graphs with bounded parameters
- A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
- Obstructions to a small hyperbolicity in Helly graphs
This page was built for publication: Graph minors. II. Algorithmic aspects of tree-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3751592)
