2026-07-23T18:00:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:59 2024-03-06T11:06:11Z ddc:004 open_access

Network Discovery and Verification Beerliova, Zuzana Eberhard, Felix Erlebach, Thomas Hall, Alexander Hoffmann, Michael Mihalak, Matus Ram, L. Shankar on-line algorithms set cover landmarks metric dimension 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zuzana Beerliova and Felix Eberhard and Thomas Erlebach and Alexander Hall and Michael Hoffmann and Matus Mihalak and L. Shankar Ram 2005 Is Part Of Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.05031.17 urn:nbn:de:0030-drops-594 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.17 eng https://creativecommons.org/licenses/by/4.0/legalcode