Grad and classes with bounded expansion. II: Algorithmic aspects

DOI10.1016/j.ejc.2006.07.014zbMath1185.05131arXivmath/0508324OpenAlexW2075921069WikidataQ56689201 ScholiaQ56689201MaRDI QIDQ2426457

Jaroslav Nešetřil, Patrice Ossona de Mendez

Publication date: 22 April 2008

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0508324

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

List rankings and on-line list rankings of graphs, Characterising bounded expansion by neighbourhood complexity, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Hypertree-depth and minors in hypergraphs, Towards a characterization of universal categories, Sublinear separators, fragility and subexponential expansion, Forbidden graphs for tree-depth, On low tree-depth decompositions, A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth, Parameterized complexity of generalized domination problems, Grad and classes with bounded expansion. I: Decompositions, Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities, Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations, Unnamed Item, On nowhere dense graphs, Many Facets of Dualities, Clustering powers of sparse graphs, Distance-two coloring of sparse graphs, How many \(F\)'s are there in \(G\)?, Colouring, constraint satisfaction, and complexity, On forbidden subdivision characterizations of graph classes, Confronting intractability via parameters, Polynomial treedepth bounds in linear colorings, A note on sublinear separators and expansion, Characterisations and examples of graph classes with bounded expansion, Computing tree-depth faster than \(2^n\), On the weak 2-coloring number of planar graphs, On classes of graphs with strongly sublinear separators, Small graph classes and bounded expansion, First order properties on nowhere dense structures, Rank-width and tree-width of \(H\)-minor-free graphs, LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth, Computing vertex-surjective homomorphisms to partially reflexive trees, Layouts of Expander Graphs, Gonality of expander graphs, On the parameterized complexity of \([1,j\)-domination problems], A distributed low tree-depth decomposition algorithm for bounded expansion classes, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Large Independent Sets in Triangle-Free Planar Graphs, Unnamed Item, Strongly Sublinear Separators and Polynomial Expansion, Balanced line separators of unit disk graphs, EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES, On the Parameterized Complexity of [1,j-Domination Problems], Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Structural sparsity of complex networks: bounded expansion in random models and real-world graphs, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Generalization of transitive fraternal augmentations for directed graphs and its applications, A surprising permanence of old motivations (a not-so-rigid story), Obstructions for Tree-depth, Counting Homomorphisms to Sparse Graphs, Structural Properties of Sparse Graphs, Erdös--Hajnal Properties for Powers of Sparse Graphs, From \(\chi\)- to \(\chi_p\)-bounded classes, Unnamed Item, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

Cites Work