Discovery of network properties with all-shortest-paths queries

DOI10.1016/J.TCS.2010.01.010MaRDI QIDQ962167zbMATH OpenOpenAlexFDO

Authors D. Bilò, Matúš Mihalák, Peter Widmayer, Thomas Erlebach

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

discoverygraph propertynetworkonline algorithmqueryshortest path

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)

Recommendations

• Discovery of Network Properties with All-Shortest-Paths Queries
• Network Discovery and Verification with Distance Queries
• Graph-Theoretic Concepts in Computer Science
• Approximate Discovery of Random Graphs
• Optimal path discovery problem with homogeneous knowledge

Cites work

• Emergence of Scaling in Random Networks
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• scientific article; zbMATH DE number 2068163 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• scientific article; zbMATH DE number 1875406 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• On recognizing graph properties from adjacency matrices

Cited in

(16)

• Optimal path discovery problem with homogeneous knowledge
• Network Discovery and Verification with Distance Queries
• Discovery of Network Properties with All-Shortest-Paths Queries
• Graph-Theoretic Concepts in Computer Science
• 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
• Distance-edge-monitoring sets of networks
• Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity
• Perturbation results for distance-edge-monitoring numbers
• Monitoring the edges of product networks using distances
• Realizability problem of distance-edge-monitoring numbers
• Greediness is not always a vice: efficient discovery algorithms for assignment problems
• The distance-edge-monitoring numbers of subdivision graphs
• Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
• Network verification via routing table queries

This page was built for publication: Discovery of network properties with all-shortest-paths queries

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