An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs

DOI10.1137/1.9781611974782.58zbMath1410.68155arXiv1604.01445OpenAlexW2340785412MaRDI QIDQ4575797

Luca Trevisan, Pierluigi Crescenzi, Michele Borassi

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Beyond Helly graphs: the diameter problem on absolute retracts ⋮ The diameter of AT‐free graphs ⋮ Finding Cliques in Social Networks: A New Distribution-Free Model ⋮ Deterministic performance guarantees for bidirectional BFS on real-world networks ⋮ Greed is good for deterministic scale-free networks ⋮ KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Parameterized complexity of diameter

This page was built for publication: An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs