Graph minors. II. Algorithmic aspects of tree-width
From MaRDI portal
Publication:3751592
DOI10.1016/0196-6774(86)90023-4zbMATH Open0611.05017OpenAlexW2029448190MaRDI QIDQ3751592FDOQ3751592
Authors: Neil Robertson, Paul Seymour 
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)
- 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
- Graph minors and parameterized algorithm design
- 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
- Combinatorics of TCP reordering
- The complexity of learning minor closed graph classes
- On the computational complexity of the bipartizing matching problem
- Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering
- Shortest path queries in digraphs of small treewidth
- Contraction-bidimensionality of geometric intersection graphs
- Space-efficient vertex separators for treewidth
- Online promise problems with online width metrics
- Monotonicity of Non-deterministic Graph Searching
- A local characterization of bounded clique-width for line graphs
- Bounding the search number of graph products
- Title not available (Why is that?)
- Comparing linear width parameters for directed graphs
- Weighted hypertree decompositions and optimal query plans
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- Boundary classes for graph problems involving non-local properties
- On the thinness and proper thinness of a graph
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- On treewidth, separators and Yao's garbling
- Disjoint Paths—A Survey
- Graph classes with and without powers of bounded clique-width
- Sublinear separators, fragility and subexponential expansion
- On the complexity of the regenerator location problem treewidth and other parameters
- On the treewidth of toroidal grids
- Structure of graphs with locally restricted crossings
- Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
- The complexity of broadcasting in planar and decomposable graphs
- The complexity of broadcasting in planar and decomposable graphs
- The first order definability of graphs with separators via the Ehrenfeucht game
- Finding cut-vertices in the square roots of a graph
- On the complexity of reasoning about opinion diffusion under majority dynamics
- Parameterized leaf power recognition via embedding into graph products
- On hyperedge replacement and BNLC graph grammars
- Contiguous search problem in Sierpiński graphs
- Tree decompositions and social graphs
- Introduction to special issue on RNA
- A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
- Title not available (Why is that?)
- Provenance circuits for trees and treelike instances
- Decomposing infinite graphs
- Title not available (Why is that?)
- Provably Shorter Regular Expressions from Deterministic Finite Automata
- Hybrid backtracking bounded by tree-decomposition of constraint networks
- Grids and their minors
- On minimum dominating sets with minimum intersection
- Maximum \(k\)-splittable \(s, t\)-flows
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Non-deterministic graph searching in trees
- 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
- Are there any good digraph width measures?
- 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
- 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?)
- 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
- Approximate tree decompositions of planar graphs in linear time
- 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
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)
