Beerliova, Zuzana ;
Eberhard, Felix ;
Erlebach, Thomas ;
Hall, Alexander ;
Hoffmann, Michael ;
Mihalak, Matus ;
Ram, L. Shankar
Network Discovery and Verification
Abstract
Consider the problem of discovering (or verifying) the edges and nonedges of a network, modelled as a connected undirected graph, using a minimum number of queries. A query at a vertex v discovers (or verifies) all edges and nonedges whose endpoints have different distance from v. In the network discovery problem, the edges and nonedges are initially unknown, and the algorithm must select the next query based only on the results of previous queries. We study the problem using competitive analysis and give a randomized online algorithm with competitive ratio O(sqrt(n*log n)) for graphs with n vertices. We also show that no deterministic algorithm can have competitive ratio better than 3. In the network verification problem, the graph is known in advance and the goal is to compute a minimum number of queries that verify all edges and nonedges. This problem has previously been studied as the problem of placing landmarks in graphs or determining the metric dimension of a graph. We show that there is no approximation algorithm for this problem with ratio o(log n) unless P=NP. Furthermore, we prove that the optimal number of queries for ddimensional hypercubes is Theta(d/log d).
BibTeX  Entry
@InProceedings{beerliova_et_al:DSP:2005:59,
author = {Zuzana Beerliova and Felix Eberhard and Thomas Erlebach and Alexander Hall and Michael Hoffmann and Matus Mihalak and L. Shankar Ram},
title = {Network Discovery and Verification},
booktitle = {Algorithms for Optimization with Incomplete Information},
year = {2005},
editor = {Susanne Albers and Rolf H. M{\"o}hring and Georg Ch. Pflug and R{\"u}diger Schultz},
number = {05031},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2005/59},
annote = {Keywords: online algorithms , set cover , landmarks , metric dimension}
}
2005
Keywords: 

online algorithms , set cover , landmarks , metric dimension 
Seminar: 

05031  Algorithms for Optimization with Incomplete Information

Issue date: 

2005 
Date of publication: 

2005 