When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-594
Go to the corresponding Portal

Beerliova, Zuzana ; Eberhard, Felix ; Erlebach, Thomas ; Hall, Alexander ; Hoffmann, Michael ; Mihalak, Matus ; Ram, L. Shankar

Network Discovery and Verification

05031.ErlebachThomas.ExtAbstract.59.pdf (0.1 MB)


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

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint Published by LZI