Sparsity. Graphs, structures, and algorithms
From MaRDI portal
Publication:419416
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
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
A polynomial excluded-minor approximation of treedepth ⋮ Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ A class of highly symmetric graphs, symmetric cylindrical constructions and their spectra ⋮ Characterising bounded expansion by neighbourhood complexity ⋮ On ultralimits of sparse graph classes ⋮ Rainbow independent sets on dense graph classes ⋮ Induced and weak induced arboricities ⋮ Safe sets in graphs: graph classes and structural parameters ⋮ Chromatic numbers of exact distance graphs ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ First order convergence of matroids ⋮ On structural parameterizations of the offensive alliance problem ⋮ Short proofs of some extremal results. II. ⋮ Stack-number is not bounded by queue-number ⋮ Limits of schema mappings ⋮ The complexity of vector partition ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Courcelle's theorem for triangulations ⋮ Parameterized complexity of graph burning ⋮ Eccentricity queries and beyond using hub labels ⋮ Limits of mappings ⋮ A tight lower bound for vertex planarization on graphs of bounded treewidth ⋮ Exact square coloring of certain classes of graphs: complexity and algorithms ⋮ Parameterized complexity of fair deletion problems ⋮ On quasi-planar graphs: clique-width and logical description ⋮ On coloring numbers of graph powers ⋮ Towards a characterization of universal categories ⋮ Polynomial expansion and sublinear separators ⋮ Induced subdivisions and bounded expansion ⋮ Grid minors in damaged grids ⋮ Fast recoloring of sparse graphs ⋮ Sublinear separators, fragility and subexponential expansion ⋮ First-order limits, an analytical perspective ⋮ On low tree-depth decompositions ⋮ Edge degeneracy: algorithmic and structural results ⋮ Treetopes and their graphs ⋮ Sparsity measure of a network graph: Gini index ⋮ Polynomial graph invariants from homomorphism numbers ⋮ 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 ⋮ 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 ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Polynomial treedepth bounds in linear colorings ⋮ Majority coloring game ⋮ 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 ⋮ Boxicity, poset dimension, and excluded minors ⋮ Computing tree-depth faster than \(2^n\) ⋮ On the complexity of broadcast domination and multipacking In digraphs ⋮ Finding temporal paths under waiting time constraints ⋮ Track layouts, layered path decompositions, and leveled planarity ⋮ On the weak 2-coloring number of planar graphs ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph ⋮ The complexity landscape of decompositional parameters for ILP ⋮ On the diameter of tree associahedra ⋮ On classes of graphs with strongly sublinear separators ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Long induced paths in graphs ⋮ On 1-uniqueness and dense critical graphs for tree-depth ⋮ Anagram-free graph colouring ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Complexity of token swapping and its variants ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number ⋮ Directed width parameters and circumference of digraphs ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Exact distance graphs of product graphs ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Colouring exact distance graphs of chordal graphs ⋮ Notes on graph product structure theory ⋮ Twin-width and generalized coloring numbers ⋮ Structural sparsity of complex networks: bounded expansion in random models and real-world graphs ⋮ \(H\)-colouring \(P_t\)-free graphs in subexponential time ⋮ On the treewidth of Hanoi graphs ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ Strict superstablity and decidability of certain generic graphs ⋮ Diameter estimates for graph associahedra ⋮ Twin-width and polynomial kernels ⋮ Excluding a ladder ⋮ Local planar domination revisited ⋮ From \(\chi\)- to \(\chi_p\)-bounded classes ⋮ How to play Thue games ⋮ Local certification of graphs with bounded genus ⋮ On monoid graphs ⋮ Fine-grained parameterized complexity analysis of graph coloring problems ⋮ A tight analysis of geometric local search ⋮ Parameterized complexity of \((A,\ell)\)-path packing ⋮ Characterising graphs with no subdivision of a wheel of bounded diameter ⋮ Proper orientations and proper chromatic number ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4 ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ Neighbourhood complexity of graphs of bounded twin-width ⋮ Parameterized intractability of defensive alliance problem ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ SAT backdoors: depth beats size ⋮ Beyond symmetry in generalized Petersen graphs ⋮ CSP beyond tractable constraint languages ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Hat Guessing Numbers of Strongly Degenerate Graphs ⋮ Kontsevich Graphons ⋮ Graph product structure for non-minor-closed classes ⋮ Efficient interprocedural data-flow analysis using treedepth and treewidth ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ Sparse graphs without long induced paths ⋮ Asymptotic behavior of Markov complexity ⋮ Bounding generalized coloring numbers of planar graphs using coin models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Harmonious and achromatic colorings of fragmentable hypergraphs ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Parameterized Complexity of Graph Burning ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Parameterized Complexity of Geodetic Set ⋮ Competitive Online Search Trees on Trees ⋮ 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
