کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429544 | 687597 | 2015 | 15 صفحه PDF | دانلود رایگان |
• Any network of n nodes needs Ω(loglogn)Ω(loglogn) queries to be verified.
• Constant diameter networks need Ω(logn)Ω(logn) queries.
• There is no o(logn)o(logn)-approximation algorithm for diameter 2 networks, unless P=NPP=NP.
• We give an O(logn)O(logn)-approximation algorithm for diameter 2 networks.
• We give exact linear-time algorithms for paths, trees, and cycles of even length.
The network verification problem is that of establishing the accuracy of a high-level description of its physical topology, by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes to be queried so as to univocally identify the graph. This problem has been studied with respect to different query models, assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path.
Journal: Journal of Computer and System Sciences - Volume 81, Issue 1, February 2015, Pages 234–248