Please use this identifier to cite or link to this item:
Title: Discovery of network properties with all-shortest-paths queries
Authors: Bilo, Davide
Erlebach, Thomas Rainer
Mihalak, Matus
Widmayer, Peter
First Published: 17-Jun-2008
Presented at: 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008), Villars sur Ollon, Switzerland, 17th - 20th June 2008
Start Date: 17-Jun-2008
End Date: 20-Jun-2008
Publisher: Springer-Verlag Berlin
Citation: Proceedings of 15th International Colloquium on Structural Information and Communication Complexity, 2008, 5058, pp. 89-103
Abstract: 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 and 2-vertex connectivity 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.
Series/Report no.: Lecture Notes in Computer Science, Vol. 5058
DOI Link: 10.1007/978-3-540-69355-0_9
ISSN: 0302-9743
ISBN: 978-3-540-69326-0
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2008, Springer Verlag. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
SIROCCO2008FinalAuthorVersion.pdfPost-review (final submitted)223.13 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.