Improved approximability and non-approximability results for graph diameter decreasing problems
- 3 February 2012
- journal article
- Published by Elsevier BV in Theoretical Computer Science
- Vol. 417, 12-22
- https://doi.org/10.1016/j.tcs.2011.05.014
Abstract
No abstract availableKeywords
This publication has 19 references indexed in Scilit:
- Augmenting forests to meet odd diameter requirementsDiscrete Optimization, 2006
- Decreasing the diameter of cyclesJournal of Graph Theory, 2003
- How to decrease the diameter of triangle-free graphsCombinatorica, 1998
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problemsOperations Research Letters, 1992
- Diameter increase caused by edge deletionJournal of Graph Theory, 1987
- A unified approach to approximation algorithms for bottleneck problemsJournal of the ACM, 1986
- Clustering to minimize the maximum intercluster distanceTheoretical Computer Science, 1985
- Diameter bounds for altered graphsJournal of Graph Theory, 1984
- The complexity of designing a network with minimum diameterNetworks, 1981
- Approximation algorithms for combinatorial problemsJournal of Computer and System Sciences, 1974