References
References
- Chepoi , V , Noltemeier , H and Vaxie , Y . 2003 . Upgrading trees under diameter and budget constraints . Networks , 41 ( 1 ) : 24 – 35 .
- Drangmeister , KU , Krumke , SO Marathe , MV . 1999 . Modifying edges of a network to obtain short subgraphs . Theoretical Computer Science , 203 : 91 – 121 .
- Krumke , SO , Marathe , MV Noltemeier , H . 1998 . Approximation algorithms for certain network improvement problems . Journal of Combinatorial Optimization , 2 : 257 – 288 .
- Krumke , SO Noltemeier , Hartmut . 1999 . Improving spanning trees by upgrading nodes . Theoretical Computer Science , 221 : 139 – 155 .
- Krumke , SO , Marathe , MV Noltemerer , H . 1999 . Improving minimum cost spanning trees by upgrading nodes . Journal of Algorithms , 33 : 92 – 111 .
- Krumke , SO , Marathe , MV Noltemerer , H . 2001 . Upgrading bottleneck constrained forests . Discrete Applied Mathematics , 108 : 129 – 142 .
- Paik , D and Sahni , S . 1995 . Network upgrading problems . Networks , 26 : 45 – 58 .
- Zhang , JZ , Yang , XG and Cai , MC . 2004 . Inapproximability and a polynomially solvable special case of a network improvement problem . European Journal of Operational Research , 155 : 251 – 257 .
- Zhang , JZ , Yang , XG and Cai , MC . 2004 . A network improvement problem under different norms . Computational Optimization and Applications , 27 : 305 – 319 .
- Ausiello G Crescenzi P Gambosi G et al. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties Berlin Springer 1999
- Hochbaum D Approximation Algorithms for NP-hard Problems Boston PWS 1997
- Papadimitriou CH Computational Complexity New York Addison-Wesley 1994
- Raz R Safra S A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP In: Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM 1997 475 484