Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Marked Items 
Alerts
Order History
Saved Items
All
Favorites
    
Book Chapter Printable view
AnFPTAS forWeight-Constrained SteinerTrees in Series-Parallel Graphs

AnFPTAS forWeight-Constrained SteinerTrees in Series-Parallel Graphs

Book SeriesLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISSN0302-9743 (Print) 1611-3349 (Online)
VolumeVolume 2108/2001
BookComputing and Combinatorics
DOI10.1007/3-540-44679-6
Copyright2001
ISBN978-3-540-42494-9
DOI10.1007/3-540-44679-6_58
Pages519-528
Subject CollectionComputer Science
SpringerLink DateMonday, January 01, 2001
Add to marked items

AnFPTAS forWeight-Constrained SteinerTrees in Series-Parallel Graphs

Guangting Chen5 Contact Information and Guoliang Xue6 Contact Information

(5)  Hongzhou Institute of Electronic Engineering, School of Science and Arts, Hongzhou, China
(6)  Department of Computer Science, University of Vermont, Burlington, VT, 05405
Abstract
In this paper, we study the problem of computing a minimum cost Steiner tree subject to weight constraint in a series-parallel graph where each edge has a nonnegative integer cost and a nonnegative integer weight.We present a fully polynomial time approximation scheme for this NP-complete problem.

Contact Information Guangting Chen
Email: gtchen@mail.hz.zj.cn

Contact Information Guoliang Xue
Email: xue@cs.uvm.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.
more options
Find


Export this chapter
Export this chapter as RIS | Text
 
Frequently asked questions | General information on journals and books | Send us your feedback | Impressum | Contact
© Springer. Part of Springer Science+Business Media
Privacy, Disclaimer, Terms and Conditions, © Copyright Information
Remote Address: 38.107.191.108 • Server: mpweb07
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)