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

DOI10.4230/LIPICS.ESA.2020.40OpenAlexW3082952831MaRDI QIDQ5874510FDOQ5874510

Authors: Jan Dreier, Philipp Kuinke, Peter Rossmanith 

Publication date: 7 February 2023

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

Recommendations

• scientific article; zbMATH DE number 7650219
• Parameterized model checking of weighted networks
• Model checking lower bounds for simple graphs
• Model checking lower bounds for simple graphs
• First-order model checking on generalisations of pushdown graphs.
• scientific article
• Graph-theoretic analysis of complex stochastic networks
• Model checking and boolean graphs
• scientific article; zbMATH DE number 1959499
• scientific article; zbMATH DE number 777287

zbMATH Keywords

random graphsaverage case analysisfirst-order model-checking

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Power-law distributions in empirical data
• A survey of statistical network models
• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• Graph clustering
• A critical point for random graphs with a given degree sequence
• Collective dynamics of `small-world' networks
• On Random Intersection Graphs: The Subgraph Problem
• Probabilities on finite models
• Computational Complexity
• Connected components in random graphs with given expected degree sequences
• Linear time solvable optimization problems on graphs of bounded clique-width
• Grad and classes with bounded expansion. I: Decompositions
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The degree sequence of a scale-free random graph process
• Random graphs.
• Title not available (Why is that?)
• The average distances in random graphs with given expected degrees
• Complex graphs and networks
• Parameterized algorithms
• Title not available (Why is that?)
• Query evaluation via tree-decompositions
• Bidimensionality and kernels
• The polynomial-time hierarchy
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• Title not available (Why is that?)
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• Deciding first-order properties of locally tree-decomposable structures
• Algorithmic Meta-theorems
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Diameter, connectivity, and phase transition of the uniform random intersection graph
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• The complexity of first-order and monadic second-order logic revisited
• The small-world phenomenon: an algorithmic perspective
• Diameters in preferential attachment models
• Graph minors. XVI: Excluding a non-planar graph
• Title not available (Why is that?)
• Average Case Complete Problems
• Logic, graphs, and algorithms
• Hyperbolicity, degeneracy, and expansion of random intersection graphs
• Algorithmic uses of the Feferman-Vaught theorem
• Title not available (Why is that?)
• Fixed-parameter tractability, definability, and model-checking
• (Meta) kernelization
• Clustering and the hyperbolic geometry of complex networks
• Hyperbolic random graphs: separators and treewidth
• Title not available (Why is that?)
• Motif Counting in Preferential Attachment Graphs
• Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size

Cited In (2)

• Title not available (Why is that?)
• Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes

Uses Software

• plfit

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

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