Recovering sparse graphs

DOI10.4230/LIPICS.MFCS.2018.29MaRDI QIDQ5005129zbMATH OpenFDO

Authors Jakub Gajarský, Daniel Král'

Publication date 4 August 2021

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

zbMATH Keywords

bounded expansiondegenerate graphsinterpretationsmodel checking

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Testing first-order properties for subclasses of sparse graphs
• Fixed-parameter tractable distances to sparse graph classes
• scientific article; zbMATH DE number 6784973

Cites work

• Algorithmic meta-theorems
• Approximating clique-width and branch-width
• Computing and combinatorics. 13th annual international conference, COCOON 2007, Banff, Canada, July 16--19, 2007. Proceedings.
• Deciding first-order properties of locally tree-decomposable structures
• Domination problems in nowhere-dense classes of graphs
• First-order interpretations of bounded expansion classes
• FO model checking of geometric graphs
• FO model checking of interval graphs
• Fundamentals of computation theory. 21st international symposium, FCT 2017, Bordeaux, France, September 11--13, 2017. Proceedings
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 1231505 (Why is no real title available?)
• Linear time low tree-width partitions and algorithmic consequences
• Linear time solvable optimization problems on graphs of bounded clique-width
• Methods for algorithmic meta theorems
• Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5--8, 2016
• Sparsity. Graphs, structures, and algorithms
• Testing first-order properties for subclasses of sparse graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(4)

• Sparse Recovery With Graph Constraints
• Recovering sparse graphs
• Twin-width. IV: Ordered graphs and matrices
• First-order transductions of graphs (invited talk)

This page was built for publication: Recovering sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5005129)