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
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Logical aspects of Cayley-graphs: the group case
- The structure of the models of decidable monadic theories of graphs
- Towards fixed-parameter tractable algorithms for abstract argumentation
- Precoloring extension. I: Interval graphs
- Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
- Minimum vertex cover in rectangle graphs
- Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Linearity of grid minors in treewidth with applications through bidimensionality
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- On the complexity of some subgraph problems
- Treewidth computations. II. Lower bounds
- Local tree-width, excluded minors, and approximation algorithms
- \(k\)-NLC graphs and polynomial algorithms
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Trimming weighted graphs of bounded treewidth
- On switching classes, NLC-width, cliquewidth and treewidth
- A 3-approximation for the pathwidth of Halin graphs
- Uniform Constraint Satisfaction Problems and Database Theory
- The treewidth and pathwidth of hypercubes
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- Characterizations and algorithmic applications of chordal graph embeddings
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Fixed-Parameter Tractability of Treewidth and Pathwidth
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Bounds on vertex colorings with restrictions on the union of color classes
- Decontamination of hypercubes by mobile agents
- A faster polynomial-space algorithm for Max 2-CSP
- Treewidth lower bounds with brambles
- Most probable explanations in Bayesian networks: complexity and tractability
- A little statistical mechanics for the graph theorist
- On tree-partition-width
- Rooted routing in the plane
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Fork-decompositions of matroids
- Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem
- Chordal embeddings of planar graphs
- The Clique-Width of Tree-Power and Leaf-Power Graphs
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- Diameter and treewidth in minor-closed graph families, revisited
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- Partition-based logical reasoning for first-order and propositional theories
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)
