Discovery of network properties with all-shortest-paths queries

DOI10.1016/j.tcs.2010.01.010zbMath1191.68028OpenAlexW2050803155MaRDI QIDQ962167

Peter Widmayer, Matúš Mihalák, Davide Bilò, Erlebach, Thomas

Publication date: 6 April 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.01.010

zbMATH Keywords

networkshortest pathgraph propertyonline algorithmquerydiscovery

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items

Monitoring the edges of a graph using distances with given girth ⋮ On the distance-edge-monitoring numbers of graphs ⋮ Erdös-Gallai-type problems for distance-edge-monitoring numbers ⋮ Monitoring the edges of a graph using distances ⋮ Network verification via routing table queries

Cites Work

• On recognizing graph properties from adjacency matrices
• Emergence of Scaling in Random Networks
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item