Network verification via routing table queries

作者：

Highlights：

• Any network of n nodes needs Ω(log⁡log⁡n) queries to be verified.

• Constant diameter networks need Ω(log⁡n) queries.

• There is no o(log⁡n)-approximation algorithm for diameter 2 networks, unless P=NP.

• We give an O(log⁡n)-approximation algorithm for diameter 2 networks.

• We give exact linear-time algorithms for paths, trees, and cycles of even length.

摘要

•Any network of n nodes needs Ω(log⁡log⁡n) queries to be verified.•Constant diameter networks need Ω(log⁡n) queries.•There is no o(log⁡n)-approximation algorithm for diameter 2 networks, unless P=NP.•We give an O(log⁡n)-approximation algorithm for diameter 2 networks.•We give exact linear-time algorithms for paths, trees, and cycles of even length.

论文关键词：Network verification,Graph/network topology,Computational complexity,Approximation algorithms

论文评审过程：Received 21 September 2011, Revised 9 April 2014, Accepted 25 April 2014, Available online 20 June 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.06.003