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)
Minimal triangulations of graphs: a survey ⋮ The treewidth and pathwidth of hypercubes ⋮ Structural tractability of counting of solutions to conjunctive queries ⋮ On computational complexity of graph inference from counting ⋮ On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity ⋮ A coloring problem for weighted graphs ⋮ Acyclic coloring parameterized by directed clique-width ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks ⋮ Approximating the pathwidth of outerplanar graphs ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ Contraction obstructions for connected graph searching ⋮ Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ Approximate tree decompositions of planar graphs in linear time ⋮ Collective tree spanners in graphs with bounded parameters ⋮ Approximation algorithms for treewidth ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs ⋮ Combinatorics of TCP reordering ⋮ On zeros of the characteristic polynomial of matroids of bounded tree-width ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Online promise problems with online width metrics ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Characterizing width two for variants of treewidth ⋮ Courcelle's theorem for triangulations ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ A local characterization of bounded clique-width for line graphs ⋮ Characterizations for restricted graphs of NLC-width 2 ⋮ Graphs with bounded tree-width and large odd-girth are almost bipartite ⋮ Some recent progress and applications in graph minor theory ⋮ Weighted hypertree decompositions and optimal query plans ⋮ Achievable sets, brambles, and sparse treewidth obstructions ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ Tractable counting of the answers to conjunctive queries ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Are there any good digraph width measures? ⋮ Sublinear separators, fragility and subexponential expansion ⋮ Graph classes with and without powers of bounded clique-width ⋮ On the complexity of the regenerator location problem treewidth and other parameters ⋮ The disjoint paths problem in quadratic time ⋮ Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs ⋮ On the treewidth of toroidal grids ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Trimming weighted graphs of bounded treewidth ⋮ A faster polynomial-space algorithm for Max 2-CSP ⋮ On switching classes, NLC-width, cliquewidth and treewidth ⋮ A hybrid tractable class for non-binary CSPs ⋮ Computing bond orders in molecule graphs ⋮ Minesweeper on graphs ⋮ On shortest disjoint paths in planar graphs ⋮ Directed NLC-width ⋮ Most probable explanations in Bayesian networks: complexity and tractability ⋮ Treewidth governs the complexity of target set selection ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ Treewidth lower bounds with brambles ⋮ Maximum \(k\)-splittable \(s, t\)-flows ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Monotonicity of non-deterministic graph searching ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ Introduction to special issue on RNA ⋮ Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition ⋮ A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs ⋮ Computing cooperative solution concepts in coalitional skill games ⋮ Algebraically grid-like graphs have large tree-width ⋮ Characterization of minimum cycle basis in weighted partial 2-trees ⋮ The inverse 1-maxian problem with edge length modification ⋮ The complexity of subgraph isomorphism for classes of partial k-trees ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ On the complexity of the multicut problem in bounded tree-width graphs and digraphs ⋮ Neighbourhood-width of trees ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Recognising \(k\)-connected hypergraphs in cubic time ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ Efficient sets in partial \(k\)-trees ⋮ Peptide sequencing via graph path decomposition ⋮ Treewidth computations. I: Upper bounds ⋮ Hypertree decompositions and tractable queries ⋮ Connected graph searching in chordal graphs ⋮ Recent developments on graphs of bounded clique-width ⋮ On the complexity of some subgraph problems ⋮ Treewidth computations. II. Lower bounds ⋮ Minimum vertex cover in rectangle graphs ⋮ Logical aspects of Cayley-graphs: the group case ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time ⋮ Girth and treewidth ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ The treewidth of line graphs ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Quantitative graph theory: a new branch of graph theory and network science ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ Complexity of abstract argumentation under a claim-centric view ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ Graph minors. III. Planar tree-width ⋮ The structure of the models of decidable monadic theories of graphs ⋮ Hybrid backtracking bounded by tree-decomposition of constraint networks
This page was built for publication: Graph minors. II. Algorithmic aspects of tree-width
