Sparsity. Graphs, structures, and algorithms
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Model theory of finite structures (03C13) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75) Graph minors (05C83)
Recommendations
- Spectral sparsification of graphs
- Sparse matrix decompositions and graph characterizations
- A general framework for graph sparsification
- A general framework for graph sparsification
- Algorithmic properties of sparse digraphs
- Structural Properties of Sparse Graphs
- Structural Properties of Sparse Graphs
- Sparse graphs: metrics and random models
- Spanners in sparse graphs
- Spanners in Sparse Graphs
Cited in
(only showing first 100 items - show all)- A note on Fiedler value of classes with sublinear separators
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Fast winning strategies for the attacker in eternal domination
- Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
- Strict superstablity and decidability of certain generic graphs
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Shallow Minors, Graph Products, and Beyond-Planar Graphs
- On the parameterized complexity of \([1,j]\)-domination problems
- From \(\chi\)- to \(\chi_p\)-bounded classes
- Random 2-cell embeddings of multistars
- On the size of minimal separators for treedepth decomposition
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- Layered separators in minor-closed graph classes with applications
- Local certification of graphs with bounded genus
- Regular partitions of gentle graphs
- Rainbow independent sets on dense graph classes
- Harmonious and achromatic colorings of fragmentable hypergraphs
- On first-order transductions of classes of graphs
- Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
- Efficient data structures for sparse network representation
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Fine-grained parameterized complexity analysis of graph coloring problems
- On the diameter of tree associahedra
- Conflict free version of covering problems on graphs: classical and parameterized
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Grid minors in damaged grids
- Clustered colouring of graph classes with bounded treedepth or pathwidth
- Towards exact structural thresholds for parameterized complexity
- How to play Thue games
- Computing treedepth in polynomial space and linear FPT time
- Turbocharging heuristics for weak coloring numbers
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- No go theorems: directed containers that do not distribute over distribution monads
- Brief announcement: Distributed model checking on graphs of bounded treedepth
- Treetopes and their graphs
- On nowhere dense graphs
- scientific article; zbMATH DE number 7204413 (Why is no real title available?)
- Lossy kernels for connected dominating set on sparse graphs
- Improved bounds for the excluded-minor approximation of treedepth
- Comparing width parameters on graph classes
- Finite integer index of pathwidth and treewidth
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Tangled paths: a random graph model from Mallows permutations
- Quantified conjunctive queries on partially ordered sets
- Product structure of graph classes with bounded treewidth
- Minimal asymmetric graphs
- Approximation algorithms for polynomial-expansion and low-density graphs
- Algebraic graph theory for sparse flexibility matrices
- Track layouts, layered path decompositions, and leveled planarity
- Shallow vertex minors, stability, and dependence
- A tight analysis of geometric local search
- A polynomial excluded-minor approximation of treedepth
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Exact square coloring of certain classes of graphs: complexity and algorithms
- Proper orientations and proper chromatic number
- Elimination Distance to Bounded Degree on Planar Graphs
- 1-subdivisions, the fractional chromatic number and the Hall ratio
- On the complexity of broadcast domination and multipacking in digraphs
- Parameterized Complexity of $$(A,\ell )$$-Path Packing
- Beyond symmetry in generalized Petersen graphs
- SAT backdoors: depth beats size
- Estimating the global density of graphs by a sparseness index
- On ultralimits of sparse graph classes
- Sparse induced subgraphs of large treewidth
- Competitive Online Search Trees on Trees
- scientific article; zbMATH DE number 7764102 (Why is no real title available?)
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Polynomial treedepth bounds in linear colorings
- The parameterized complexity landscape of the unsplittable flow problem
- Approximation algorithms for treewidth, pathwidth, and treedepth -- a short survey
- Subchromatic numbers of powers of graphs with excluded minors
- Recovering sparse graphs
- A class of highly symmetric graphs, symmetric cylindrical constructions and their spectra
- Characterising bounded expansion by neighbourhood complexity
- Orthogonal tree decompositions of graphs
- Harary polynomials
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Compound logics for modification problems
- Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
- On the weak 2-coloring number of planar graphs
- Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces
- On fractional fragility rates of graph classes
- Majority coloring game
- An algorithmic framework for locally constrained homomorphisms
- Kernelization for feedback vertex set via elimination distance to a forest
- Counting Homomorphic Cycles in Degenerate Graphs
- Track layout is hard
- CSP beyond tractable constraint languages
- Tangled paths: a random graph model from Mallows permutations (extended abstract)
- Decomposition horizons: from graph sparsity to model-theoretic dividing lines (extended abstract)
- Monadic NIP in monotone classes of relational structures (extended abstract)
- Uniform orderings for generalized coloring numbers
- Induced and weak induced arboricities
- Safe sets in graphs: graph classes and structural parameters
- On monoid graphs
- A distributed low tree-depth decomposition algorithm for bounded expansion classes
- Graph product structure for non-minor-closed classes
- Local certification of geometric graph classes
This page was built for publication: Sparsity. Graphs, structures, and algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q419416)
