Sparsity. Graphs, structures, and algorithms

DOI10.1007/978-3-642-27875-4zbMath1268.05002OpenAlexW4253175698WikidataQ55868072 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

zbMATH Keywords

first-order logicdensityhomomorphismmodel theorygraph minorsparsitytree-depth

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Related Items (only showing first 100 items - show all)

Clustered colouring of graph classes with bounded treedepth or pathwidth ⋮ Parameterized Complexity of $$(A,\ell )$$-Path Packing ⋮ Counting Subgraphs in Degenerate Graphs ⋮ Tree densities in sparse graph classes ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Parameterized Algorithms for Queue Layouts ⋮ Parameterized Complexity of Geodetic Set ⋮ Twin-width II: small classes ⋮ Modeling limits in hereditary classes: reduction and application to trees ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Harary polynomials ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Edge Exchangeable Models for Interaction Networks ⋮ Exact square coloring of subcubic planar graphs ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Random 2-cell embeddings of multistars ⋮ 1-subdivisions, the fractional chromatic number and the Hall ratio ⋮ An annotated bibliography on 1-planarity ⋮ Layered separators in minor-closed graph classes with applications ⋮ Minimal asymmetric graphs ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ 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 ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Quantified Conjunctive Queries on Partially Ordered Sets ⋮ Finite Integer Index of Pathwidth and Treewidth ⋮ Parameterized extension complexity of independent set and related problems ⋮ Meta-kernelization using well-structured modulators ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more ⋮ A heuristic approach to the treedepth decomposition problem for large graphs ⋮ A general purpose algorithm for counting simple cycles and simple paths of any length ⋮ Local 2-separators ⋮ Two lower bounds for $p$-centered colorings ⋮ Parameterized complexity of envy-free resource allocation in social networks ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Safe Sets in Graphs: Graph Classes and Structural Parameters ⋮ Long induced paths in minor-closed graph classes and beyond ⋮ Computing partial hypergraphs of bounded width ⋮ Unnamed Item ⋮ Track Layout Is Hard ⋮ Unnamed Item ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ A note on Fiedler value of classes with sublinear separators ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ 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 ⋮ The Effect of Planarization on Width ⋮ Parameterized Algorithms for Book Embedding Problems ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. ⋮ Obstructions for Bounded Branch-depth in Matroids ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Temporal graph classes: a view through temporal separators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Many large eigenvalues in sparse graphs ⋮ The Effect of Planarization on Width ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Scattered Classes of Graphs ⋮ Feedback edge sets in temporal graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs ⋮ Unnamed Item ⋮ Strongly Sublinear Separators and Polynomial Expansion ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exact Distance Colouring in Trees ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES ⋮ Elimination Distance to Bounded Degree on Planar Graphs ⋮ First order limits of sparse graphs: Plane trees and path-width ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions ⋮ Colouring and Covering Nowhere Dense Graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Improved Bounds for the Excluded-Minor Approximation of Treedepth ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs ⋮ Subexponential parameterized algorithms for graphs of polynomial growth ⋮ Unnamed Item ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ Parameterized Algorithms for Queue Layouts ⋮ Unnamed Item ⋮ Circumference and Pathwidth of Highly Connected Graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness ⋮ Action convergence of operators and graphs

This page was built for publication: Sparsity. Graphs, structures, and algorithms