Rights / licenseIn Copyright - Non-Commercial Use Permitted
We consider the problem of discovering properties (such as the diameter) of an unknown network G(V,E) with a minimum number of queries. Initially, only the vertex set V of the network is known. Information about the edges and non-edges of the network can be obtained by querying nodes of the network. A query at a node q ∈ V returns the union of all shortest paths from q to all other nodes in V . We study the problem as an online problem – an algorithm does not initially know the edge set of the network, and has to decide where to make the next query based on the information that was gathered by previous queries. We study how many queries are needed to discover the diameter, a minimal dominating set, a maximal independent set, the minimum degree, and the maximum degree of the network. We also study the problem of deciding with a minimum number of queries whether the network is 2-edge or 2-vertex connected. We use the usual competitive analysis to evaluate the quality of online algorithms, i.e., we compare online algorithms with optimum offline algorithms. For all properties except maximal independent set, 2-vertex connectivity and minimum/maximum degree, we present and analyze online algorithms. Furthermore we show, for all the aforementioned properties, that “many” queries are needed in the worst case. As our query model delivers more information about the network than the measurement heuristics that are currently used in practise, these negative results suggest that a similar behavior can be expected in realistic settings, or in more realistic models derived from the all-shortest-paths query model Show more
Journal / seriesTechnical Report
PublisherDepartment of Computer Science, ETH
SubjectNETZWERKÜBERWACHUNG + NETZWERKADMINISTRATION (COMPUTERSYSTEME); ROUTING (COMPUTER SYSTEMS); NETWORK MONITORING (COMPUTER SYSTEMS); WEGEERMITTLUNG (COMPUTERSYSTEME)
Organisational unit03340 - Widmayer, Peter
02150 - Departement Informatik / Department of Computer Science
NotesWeitere Autoren: Thomas Erlebach, Matúš Mihalák, and Peter Widmayer.
Also published in: Structural Information and Communication Complexity, Lecture Notes in Computer Science, Volume 5058, ISBN 978-3-540-69326-0, DOI 10.1007/978-3-540-69355-0_9, Springer Berlin, pages 89-103, Technical Reports D-INFK.
MoreShow all metadata