Network Discovery and Verification with Distance Queries

DOI10.1007/11758471_10MaRDI QIDQ3434544zbMATH OpenOpenAlexFDO

Authors

Publication date 2 May 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11758471_10

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Graph-Theoretic Concepts in Computer Science
• Discovery of network properties with all-shortest-paths queries
• Discovery of Network Properties with All-Shortest-Paths Queries
• Network verification via routing table queries
• Graph reconstruction and verification

Cited in

(18)

• Reconstruction and verification of chordal graphs with a distance oracle
• Distance Queries in Large-Scale Fully Dynamic Complex Networks
• Economical graph discovery
• Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries
• The covert set-cover problem with application to network discovery
• Near-linear query complexity for graph inference
• Discovery of Network Properties with All-Shortest-Paths Queries
• Approximate Discovery of Random Graphs
• Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs
• Reachability and Distance Queries via 2-Hop Labels
• Graph reconstruction and verification
• Towards Fewer Seeds for Network Discovery
• Graph-Theoretic Concepts in Computer Science
• A study of upper ideal relation graphs of rings
• Learning hypertrees from shortest path queries
• 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: Network Discovery and Verification with Distance Queries

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