First-Order Model-Checking in Random Graphs and Complex Networks

DOI10.4230/LIPIcs.ESA.2020.40OpenAlexW3082952831MaRDI QIDQ5874510

Jan Dreier, Philipp Kuinke, Peter Rossmanith

Publication date: 7 February 2023

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

zbMATH Keywords

random graphsaverage case analysisfirst-order model-checking

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes

Uses Software

• plfit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Graph clustering
• Algorithmic uses of the Feferman-Vaught theorem
• Diameters in preferential attachment models
• The polynomial-time hierarchy
• Graph minors. XVI: Excluding a non-planar graph
• Connected components in random graphs with given expected degree sequences
• The complexity of first-order and monadic second-order logic revisited
• Linear time solvable optimization problems on graphs of bounded clique-width
• Diameter, connectivity, and phase transition of the uniform random intersection graph
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• Grad and classes with bounded expansion. I: Decompositions
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Fixed-Parameter Tractability, Definability, and Model-Checking
• The degree sequence of a scale-free random graph process
• Emergence of Scaling in Random Networks
• (Meta) Kernelization
• The small-world phenomenon
• Deciding first-order properties of locally tree-decomposable structures
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Query evaluation via tree-decompositions
• Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs
• Algorithmic Meta-theorems
• Power-Law Distributions in Empirical Data
• Average Case Complete Problems
• Probabilities on finite models
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• On Random Intersection Graphs: The Subgraph Problem
• Hyperbolic Random Graphs: Separators and Treewidth
• A New Perspective on FO Model Checking of Dense Graph Classes
• Deciding First-Order Properties of Nowhere Dense Graphs
• A critical point for random graphs with a given degree sequence
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• A Survey of Statistical Network Models
• Computational Complexity
• Collective dynamics of ‘small-world’ networks
• Bidimensionality and Geometric Graphs
• The average distances in random graphs with given expected degrees
• Parameterized Algorithms
• Clustering and the Hyperbolic Geometry of Complex Networks
• Motif Counting in Preferential Attachment Graphs
• Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size

This page was built for publication: First-Order Model-Checking in Random Graphs and Complex Networks