Diameter and treewidth in minor-closed graph families
From MaRDI portal
Publication:1578412
DOI10.1007/s004530010020zbMath0963.05128arXivmath/9907126OpenAlexW2067431706WikidataQ56235108 ScholiaQ56235108MaRDI QIDQ1578412
Publication date: 27 August 2000
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9907126
diametertreewidthtree decompositiongraph algorithmsplanar graphapproximation algorithmsapex graphsubgraph isomorphism algorithms
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Minimum Cuts in Surface Graphs ⋮ Graph separators: A parameterized view ⋮ Clustered 3-colouring graphs of bounded degree ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Parameterized Complexity of Firefighting Revisited ⋮ Obstructions to a small hyperbolicity in Helly graphs ⋮ How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ Degree-constrained decompositions of graphs: Bounded treewidth and planarity ⋮ Tree-decompositions with bags of small diameter ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ An existential locality theorem ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics ⋮ Roman domination in subgraphs of grids ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Minors and dimension ⋮ Tree-width and dimension ⋮ Complexity of edge monitoring on some graph classes ⋮ Layered separators in minor-closed graph classes with applications ⋮ Some recent progress and applications in graph minor theory ⋮ On the dimension of posets with cover graphs of treewidth 2 ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ A Note on the Minimum H-Subgraph Edge Deletion ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Sublinear separators, fragility and subexponential expansion ⋮ Target set selection with maximum activation time ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ The complexity of two graph orientation problems ⋮ On low tree-depth decompositions ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph ⋮ Approximating sparse quadratic programs ⋮ Burn and win ⋮ Domination and convexity problems in the target set selection model ⋮ Approximation algorithms via contraction decomposition ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ On fractional fragility rates of graph classes ⋮ A PTAS for the Cluster Editing Problem on Planar Graphs ⋮ Local search: is brute-force avoidable? ⋮ Extended dynamic subgraph statistics using \(h\)-index parameterized data structures ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Guard games on graphs: keep the intruder out! ⋮ Parameterizing cut sets in a graph by the number of their components ⋮ Unnamed Item ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Implicit branching and parameterized partial cover problems ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Parameterized complexity of firefighting ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Succinct certification of monotone circuits ⋮ The degree-diameter problem for sparse graph classes ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter ⋮ Frameworks for designing in-place graph algorithms ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Improved approximation algorithms for projection games ⋮ Complexity of Grundy coloring and its variants ⋮ High-dimensional structure estimation in Ising models: local separation criterion ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ Recent developments on graphs of bounded clique-width ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ Homomorphism preservation on quasi-wide classes ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Irreducible 4-critical triangle-free toroidal graphs ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Counting Subgraphs in Relational Event Graphs ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Unnamed Item ⋮ Minimizing the Oriented Diameter of a Planar Graph ⋮ 1-planarity testing and embedding: an experimental study ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs
