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)
- 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
- Combinatorics of TCP reordering
- The complexity of learning minor closed graph classes
- Provenance Circuits for Trees and Treelike Instances
- On the computational complexity of the bipartizing matching problem
- Shortest path queries in digraphs of small treewidth
- Space-efficient vertex separators for treewidth
- Online promise problems with online width metrics
- Structure of Graphs with Locally Restricted Crossings
- 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
- Graph Minors and Parameterized Algorithm Design
- 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
- Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
- 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
- Backdoors to tractable answer set programming
- 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?)
- Contraction-Bidimensionality of Geometric Intersection Graphs
- 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
- Directed NLC-width
- On the complexity of rainbow coloring problems
- Efficient sets in partial \(k\)-trees
- Layered separators in minor-closed graph classes with applications
- Quantitative graph theory: a new branch of graph theory and network science
- Heuristic and metaheuristic methods for computing graph treewidth
- Orthogonal planarity testing of bounded treewidth graphs
- Connected graph searching in chordal graphs
- On compact and efficient routing in certain graph classes
- Algorithms for generalized vertex-rankings of partial k-trees
- Algorithms and Complexity for Turaev-Viro Invariants
- On the colored Tutte polynomial of a graph of bounded treewidth
- Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition
- FINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT
- Vertex disjoint paths on clique-width bounded graphs
- A computational-level explanation of the speed of goal inference
- An approximation algorithm for computing longest paths.
- A fixed-parameter algorithm for guarding 1.5D terrains
- The word problem for free adequate semigroups
- A \(c^k n\) 5-approximation algorithm for treewidth
- FPT and kernelization algorithms for the induced tree problem
- Augmenting outerplanar graphs to meet diameter requirements
- On the maximum cardinality search lower bound for treewidth
- The treewidth of line graphs
- Minimum self-repairing graphs
- An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
- Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
- The complexity of graph languages generated by hyperedge replacement
- Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor
- Achievable sets, brambles, and sparse treewidth obstructions
- Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
- Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$
- On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
- \(K_{a,k}\) minors in graphs of bounded tree-width
- Line planning, path constrained network flow and inapproximability
- Graphs with bounded tree-width and large odd-girth are almost bipartite
- Recognising \(k\)-connected hypergraphs in cubic time
- A Local Search Algorithm for Branchwidth
- Characterizations for restricted graphs of NLC-width 2
- Some recent progress and applications in graph minor theory
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Optimization for first order Delaunay triangulations
- Graph coloring with no large monochromatic components
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)
