On the external validity of average-case analyses of graph algorithms

DOI10.4230/LIPICS.ESA.2022.21MaRDI QIDQ6969665zbMATH OpenFDO

Authors Thomas Bläsius, Philipp Fischbeck

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.21

zbMATH Keywords

average caseempirical evaluationnetwork models

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs
• Average distance queries through weighted samples in graphs and metric spaces: high scalability with tight statistical guarantees
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Collective dynamics of `small-world' networks
• Connected components in random graphs with given expected degree sequences
• Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
• Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs.
• Emergence of Scaling in Random Networks
• Exact algorithms for maximum independent set
• Fast computation of empirically tight bounds for the diameter of massive graphs
• Fast unfolding of communities in large networks
• Finding cliques in social networks: a new distribution-free model
• Geometric inhomogeneous random graphs
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3936510 (Why is no real title available?)
• Improved upper bounds for vertex cover
• KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
• Listing all maximal cliques in large sparse real-world graphs
• Listing all maximal cliques in sparse graphs in near-optimal time
• On computing the diameter of real-world undirected graphs
• Parameterized algorithms
• Reducibility among combinatorial problems
• Solving the maximum clique and vertex coloring problems on very large sparse networks
• Solving vertex cover in polynomial time on hyperbolic random graphs
• The average distances in random graphs with given expected degrees
• The complexity of theorem-proving procedures
• Understanding the effectiveness of data reduction in public transportation networks

This page was built for publication: On the external validity of average-case analyses of graph algorithms

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