| Autor: |
Kratsch, Dieter, Beerliova, Zuzana, Eberhard, Felix, Erlebach, Thomas, Hall, Alexander, Hoffmann, Michael, Mihaľák, Matúš, Ram, L. Shankar |
| Zdroj: |
Graph-Theoretic Concepts in Computer Science (9783540310006); 2005, p127-138, 12p |
| Abstrakt: |
Consider the problem of discovering (or verifying) the edges and non-edges of a network, modeled 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 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 a graph 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 . [ABSTRACT FROM AUTHOR] |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
