First-Order Model-Checking in Random Graphs and Complex Networks
From MaRDI portal
Publication:5874510
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
Related Items (1)
Uses Software
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