Abstract
We study an extension of the set cover problem, the connected set cover problem, the problem is to find a set cover of minimal size that satisfies some connectivity constraint. We first propose two algorithms that find optimal solutions for two cases, respectively, and then we propose one approximation algorithm for a special case that has the best possible performance ratio. At last we consider how to apply the obtained result to solve a wavelength assignment problem in all optical networks.
This work was supported in part by the National Natural Science Foundation of China under Grant No. 70221001, 60373012 and 10531070.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Briers, A.: Incorporating connectivity into reserve selection procedures. Biological Conservation 14, 342–355 (2000)
Chvátal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4, 233–235 (1979)
Feige, U.: A threshold of ln n for aproximating set cover. In: Proc. 28th ACM Symposium on Theory of Computing, pp. 314–318 (1996)
Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9, 256–278 (1974)
Possingham, H., Ball, I., Andelman, S.: Mathematical methods for representative reserve networks. In: Ferson, S., Burgman, M. (eds.) Quantitative Methods for Conservation Biology, pp. 291–306. Springer, New York (2000)
Ramaswami, R., Sasaki, G.: Multiwavelength optical networks with limited wavelength conversion. IEEE/ACM Transactions on Networking 6(6), 744–754 (1998)
Ruan, L., Du, D.-Z., Hu, X.-D., Jia, X.-H., Li, D.-Y., Sun, Z.: Converter placement supporting broadcast in WDM networks. IEEE Transactions on Computers 50(7), 750–758 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shuai, TP., Hu, XD. (2006). Connected Set Cover Problem and Its Applications. In: Cheng, SW., Poon, C.K. (eds) Algorithmic Aspects in Information and Management. AAIM 2006. Lecture Notes in Computer Science, vol 4041. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11775096_23
Download citation
DOI: https://doi.org/10.1007/11775096_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35157-3
Online ISBN: 978-3-540-35158-0
eBook Packages: Computer ScienceComputer Science (R0)