License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05031.17
URN: urn:nbn:de:0030-drops-594
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/59/
Go to the corresponding Portal

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

Network Discovery and Verification

pdf-format:
05031.ErlebachThomas.ExtAbstract.59.pdf (0.05 MB)

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:DagSemProc.05031.17,
  author =	{Beerliova, Zuzana and Eberhard, Felix and Erlebach, Thomas and Hall, Alexander and Hoffmann, Michael and Mihalak, Matus and Ram, L. Shankar},
  title =	{{Network Discovery and Verification}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/59},
  URN =		{urn:nbn:de:0030-drops-594},
  doi =		{10.4230/DagSemProc.05031.17},
  annote =	{Keywords: on-line algorithms , set cover , landmarks , metric dimension}
}

Keywords: on-line algorithms , set cover , landmarks , metric dimension
Collection: 05031 - Algorithms for Optimization with Incomplete Information
Issue Date: 2005
Date of publication: 30.05.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI