Sublinear separators, fragility and subexponential expansion
From MaRDI portal
Publication:896068
DOI10.1016/J.EJC.2015.09.001zbMath1327.05316arXiv1404.7219OpenAlexW2158237076MaRDI QIDQ896068
Publication date: 11 December 2015
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.7219
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
PTAS for Sparse General-valued CSPs ⋮ On weighted sublinear separators ⋮ On fractional fragility rates of graph classes ⋮ On classes of graphs with strongly sublinear separators ⋮ Strongly Sublinear Separators and Polynomial Expansion ⋮ Notes on graph product structure theory ⋮ Uniform local amenability implies Property A
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Characterisations and examples of graph classes with bounded expansion
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Graph minors. III. Planar tree-width
- On forbidden subdivision characterizations of graph classes
- Planar separators and parallel polygon triangulation.
- Small graph classes and bounded expansion
- Small topological complete subgraphs of ``dense graphs
- The isoperimetric number of random regular graphs
- Diameter and treewidth in minor-closed graph families
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Shortest paths in directed planar graphs with negative lengths
- Compact topological minors in graphs
- A separator theorem for graphs of bounded genus
- An extremal function for contractions of graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- Separator-Based Sparsification II: Edge and Vertex Connectivity
- Approximation algorithms for NP-complete problems on planar graphs
- Kernelization and Sparseness: the case of Dominating Set
- Topological cliques in graphs II
- Testing first-order properties for subclasses of sparse graphs
- Contraction decomposition in h-minor-free graphs and algorithmic applications
This page was built for publication: Sublinear separators, fragility and subexponential expansion
