Modifying networks to obtain low cost trees [electronic resource].
- Published:
- Washington, D.C. : United States. Dept. of Energy, 1996.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy. - Physical Description:
- 12 pages : digital, PDF file
- Additional Creators:
- Los Alamos National Laboratory, United States. Department of Energy, and United States. Department of Energy. Office of Scientific and Technical Information
Access Online
- Restrictions on Access:
- Free-to-read Unrestricted online access
- Summary:
- We consider the problem of reducing the edge lengths of a given network so that the modified network has a spanning tree of small total length. It is assumed that each edge e of the given network has an associated function C{sub e} that specifies the cost of shortening the edge by a given amount and that there is a budget B on the total reduction cost. The goal is to develop a reduction strategy satisfying the budget constraint so that the total length of a minimum spanning tree in the modified network is the smallest possible over all reduction strategies that obey the budget constraint. We show that in general the problem of computing optimal reduction strategy for modifying the network as above in NP-hard and present the first polynomial time approximation algorithms for the problem, where the cost functions C{sub e} are allowed to be taken from a broad class of functions. We also present improved approximation algorithms for the class of treewidth-bounded graphs when the cost functions are linear. Our results can be extended to obtain approximation algorithms for more general network design problems such as those considered in [GW, GG+94].
- Report Numbers:
- E 1.99:la-ur--96-1376
E 1.99: conf-9606220--1
conf-9606220--1
la-ur--96-1376 - Subject(s):
- Other Subject(s):
- Note:
- Published through SciTech Connect.
07/01/1996.
"la-ur--96-1376"
" conf-9606220--1"
"DE96010934"
22. workshop on graph theoretic concepts in computer science, Como (Italy), Jun 1996.
Marathe, M.V.; Ravi, S.S.; Krumke, S.O.; Noltemeier, H.; Drangmeister, K.U. - Funding Information:
- W-7405-ENG-36
View MARC record | catkey: 14351202