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 non-edges 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 non-edges whose endpoints have different distance from v. In the network discovery problem, the edges and non-edges 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 on-line 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 non-edges. 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 d-dimensional 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 = {1862-4405},
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: on-line algorithms , set cover , landmarks , metric dimension}
}
|
Keywords: |
|
on-line algorithms , set cover , landmarks , metric dimension |
|
Seminar: |
|
05031 - Algorithms for Optimization with Incomplete Information
|
|
Issue date: |
|
2005 |
|
Date of publication: |
|
30.05.2005 |
