Sparsity. Graphs, structures, and algorithms
From MaRDI portal
Publication:419416
DOI10.1007/978-3-642-27875-4zbMath1268.05002WikidataQ55868072 ScholiaQ55868072MaRDI QIDQ419416
Jaroslav Nešetřil, Patrice Ossona de Mendez
Publication date: 18 May 2012
Published in: Algorithms and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-27875-4
05-02: Research exposition (monographs, survey articles) pertaining to combinatorics
05C75: Structural characterization of families of graphs
05C83: Graph minors
05C85: Graph algorithms (graph-theoretic aspects)
03C13: Model theory of finite structures
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C42: Density (toughness, etc.)
Related Items
On ultralimits of sparse graph classes, First order convergence of matroids, Short proofs of some extremal results. II., Kernelization using structural parameters on sparse graph classes, Courcelle's theorem for triangulations, Grid minors in damaged grids, Colouring edges with many colours in cycles, Decomposition of bounded degree graphs into \(C_4\)-free subgraphs, Practical algorithms for MSO model-checking on tree-decomposable graphs, Computing tree-depth faster than \(2^n\), Long induced paths in graphs, Boxicity, poset dimension, and excluded minors, Complexity of token swapping and its variants, Directed width parameters and circumference of digraphs, Fast recoloring of sparse graphs, Sublinear separators, fragility and subexponential expansion, First-order limits, an analytical perspective, On low tree-depth decompositions, Polynomial graph invariants from homomorphism numbers, A class of highly symmetric graphs, symmetric cylindrical constructions and their spectra, Characterising bounded expansion by neighbourhood complexity, Induced and weak induced arboricities, Safe sets in graphs: graph classes and structural parameters, Chromatic numbers of exact distance graphs, Limits of schema mappings, Towards a characterization of universal categories, Polynomial expansion and sublinear separators, Induced subdivisions and bounded expansion, Majority coloring game, Track layouts, layered path decompositions, and leveled planarity, The complexity landscape of decompositional parameters for ILP, On classes of graphs with strongly sublinear separators, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, On 1-uniqueness and dense critical graphs for tree-depth, Anagram-free graph colouring, Parameterized complexity of length-bounded cuts and multicuts, Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph, On the diameter of tree associahedra, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Faster algorithms for counting subgraphs in sparse graphs, Parameterized complexity of fair deletion problems, On quasi-planar graphs: clique-width and logical description, On coloring numbers of graph powers, Edge degeneracy: algorithmic and structural results, Treetopes and their graphs, Sparsity measure of a network graph: Gini index, Polynomial kernels for hitting forbidden minors under structural parameterizations, On fractional fragility rates of graph classes, Parameterized algorithms for book embedding problems, Clustering powers of sparse graphs, The power of linear-time data reduction for maximum matching, Regular partitions of gentle graphs, On structural parameterizations of the bounded-degree vertex deletion problem, Polynomial treedepth bounds in linear colorings, Branch-depth: generalizing tree-depth of graphs, Uniform orderings for generalized coloring numbers, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, A note on sublinear separators and expansion, Turing kernelization for finding long paths in graph classes excluding a topological minor, On the parameterized complexity of \([1,j\)-domination problems], Width, depth, and space: tradeoffs between branching and dynamic programming, Exact distance graphs of product graphs, Colouring exact distance graphs of chordal graphs, Structural sparsity of complex networks: bounded expansion in random models and real-world graphs, \(H\)-colouring \(P_t\)-free graphs in subexponential time, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?, Strict superstablity and decidability of certain generic graphs, How to play Thue games, Limits of mappings, A tight lower bound for vertex planarization on graphs of bounded treewidth, An annotated bibliography on 1-planarity, Layered separators in minor-closed graph classes with applications, Minimal asymmetric graphs, Fixed-parameter tractable distances to sparse graph classes, Linear kernels for outbranching problems in sparse digraphs, The book thickness of 1-planar graphs is constant, The \(k\)-strong induced arboricity of a graph, Parameterized extension complexity of independent set and related problems, Meta-kernelization using well-structured modulators, A general purpose algorithm for counting simple cycles and simple paths of any length, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, A note on Fiedler value of classes with sublinear separators, Interpreting nowhere dense graph classes as a classical notion of model theory, Distance-two coloring of sparse graphs, On the tree-depth of random graphs, Many large eigenvalues in sparse graphs, Modeling limits in hereditary classes: reduction and application to trees, Exact square coloring of subcubic planar graphs, Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs, 1-subdivisions, the fractional chromatic number and the Hall ratio, Strongly Sublinear Separators and Polynomial Expansion, Colouring and Covering Nowhere Dense Graphs, Quantified Conjunctive Queries on Partially Ordered Sets, Finite Integer Index of Pathwidth and Treewidth, Safe Sets in Graphs: Graph Classes and Structural Parameters, Track Layout Is Hard, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Edge Exchangeable Models for Interaction Networks, The Effect of Planarization on Width, Orthogonal Tree Decompositions of Graphs, The Effect of Planarization on Width, Scattered Classes of Graphs, Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Distributed Dominating Set Approximations beyond Planar Graphs, First order limits of sparse graphs: Plane trees and path-width, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Improved Bounds for the Excluded-Minor Approximation of Treedepth, Unnamed Item, A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth, Parameterized Algorithms for Book Embedding Problems, Large Independent Sets in Triangle-Free Planar Graphs, Exact Distance Colouring in Trees, EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES, An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Circumference and Pathwidth of Highly Connected Graphs, Harmonious and achromatic colorings of fragmentable hypergraphs, On the generalised colouring numbers of graphs that exclude a fixed minor, Temporal graph classes: a view through temporal separators, Conflict free version of covering problems on graphs: classical and parameterized, A distributed low tree-depth decomposition algorithm for bounded expansion classes, Subgraph isomorphism on graph classes that exclude a substructure, Erdös--Hajnal Properties for Powers of Sparse Graphs, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Two lower bounds for $p$-centered colorings
