Network discovery and verification with distance queries
Network discovery and verification with distance queries
复制标题
DOI：
10.1007/11758471_10
复制
发表时间：
2006-01-01
期刊：
影响因子：
--
通讯作者：
Mihalak, Matus
中科院分区：
文献类型：
--
作者：
Erlebach, Thomas;Hall, Alexander;Mihalak, Matus
网络发现（验证）问题要求在无向图G =（V，E）中的查询V的最小子集Q子集，使得这些查询发现图的所有边和非边。在距离查询模型中，在节点q处的查询返回从q到图中所有其他节点的距离。在在线网络发现问题中，图最初是未知的，并且算法必须仅基于先前查询的结果逐个选择查询。给出了一个具有竞争比为O（root nlog n）的n节点图的随机在线算法。我们还显示了欧米茄（根n）和欧米茄（log n）的确定性和随机在线算法的竞争比的下界，分别。在离线网络验证问题中，图是事先已知的，问题是计算验证所有边和非边的最小查询次数。我们证明了该问题是NP-困难的，并提出了一个O（log n）-近似算法。
The network discovery (verification) problem asks for a minimum subset Q subset of V of queries in an undirected graph G = (V, E) such that these queries discover all edges and non-edges of the graph. In the distance query model, a query at node q returns the distances from q to all other nodes in the graph. In the on-line network discovery problem, the graph is initially unknown, and the algorithm has to select queries one by one based only on the results of previous queries. We give a randomized on-line algorithm with competitive ratio O(root n log n) for graphs on n nodes. We also show lower bounds of Omega(root n) and Omega(log n) on the competitive ratio of deterministic and randomized on-line algorithms, respectively. In the off-line network verification problem, the graph is known in advance and the problem is to compute a minimum number of queries that verify all edges and non-edges. We show that the problem is NP-hard and present an O(log n)-approximation algorithm.