Powers of graphs
- 1 January 1984
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 324-333
- https://doi.org/10.1145/800057.808697
Abstract
In this paper we investigate a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design. Each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. In addition, for several of these problems we can show that unless P&eqil;NP, there does not exist a polynomial-time algorithm that has a better performance guarantee.This publication has 0 references indexed in Scilit: