Approximate Discovery of Random Graphs

DOI10.1007/978-3-540-74871-7_8MaRDI QIDQ3608500zbMATH OpenOpenAlexFDO

Authors Thomas Erlebach, Alexander Hall, Matúš Mihalák

Publication date 5 March 2009

Published in Stochastic Algorithms: Foundations and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74871-7_8

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10)

Recommendations

• Network Discovery and Verification with Distance Queries
• Finding paths in sparse random graphs requires many queries
• Graph-Theoretic Concepts in Computer Science
• Edge and pair queries-random graphs and complexity
• On the subgraph query problem

Cited in

(9)

• Topology discovery of sparse random graphs with few participants
• Finding paths in sparse random graphs requires many queries
• Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries
• Discovery of Network Properties with All-Shortest-Paths Queries
• Edge and pair queries-random graphs and complexity
• Greediness is not always a vice: efficient discovery algorithms for assignment problems
• Reconstructing random graphs from distance queries
• Network verification via routing table queries
• Discovery of network properties with all-shortest-paths queries

This page was built for publication: Approximate Discovery of Random Graphs

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