Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43741
Full metadata record
???org.dspace.app.webui.jsptag.ItemTag.dcfield??? | Value | Language |
---|---|---|
dc.contributor.advisor | 呂學一(Hsueh-I Lu) | |
dc.contributor.author | Wei-Yang Liu | en |
dc.contributor.author | 劉偉揚 | zh_TW |
dc.date.accessioned | 2021-06-15T02:27:22Z | - |
dc.date.available | 2012-08-20 | |
dc.date.copyright | 2009-08-20 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-08-17 | |
dc.identifier.citation | [1] A. Agrawal, P. Klein, and R. Ravi. When trees collide: an approximation algorithm for the generalized Steiner problem on networks. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 134–144, 1991.
[2] P. Berman and V. Ramaiyer. Improved approximations for the Steiner tree problem. Journal of Algorithms, 17:381–408, 1994. [3] M. Bern and P. Plassmann. The Steiner tree problem with edge lengths 1 and 2. Information Processing Letter, 32:171–176, 1989. [4] T. Chakraborty, J. Chuzhoy, and S. Khanna. Network design for vertex connectivity. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 167–176, 2008. [5] X. Cheng, Y. Li, D.-Z. Du, and H. Q. Ngo. Steiner trees in industry. In Handbook of Combinatorial Optimization. Kluwer Academic, 2006. [6] J. Chuzhoy and S. Khanna. Algorithms for single-source vertex connectivity. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pages 105–114, 2008. [7] A. E. F. Clementi and L. Trevisan. Improved non-approximability results for minimum vertex cover with density constraints. In Proceedings of the 2nd Annual International Conference on Computing and Combinatorics, pages 333–342, 1996. [8] Z. Galil and G. F. Italiano. Reducing edge connectivity to vertex connectivity. ACM SIGACT News, 22:57–61, 1991. [9] M. X. Goemans, A. V. Goldberg, E. Tardos, S. A. Plotkin, D. B. Shmoys, and D. P. Williamson. Improved approximation algorithms for network design problems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 223–232, 1994. [10] S. Hougardy and H. J. Prommel. A 1.598 approximation algorithm for the Steiner problem in graphs. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 448–454, 1999. [11] S. Hsieh, S.Y. Yag. Approximating the selected internal Steiner tree. Theoretical Computer Science, 381:288–291, 2007. [12] S.-Y. Hsieh, H.-M. Gao, and S.-C. Yang. On the internal Steiner tree problem. In Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation, pages 274–283, 2007. [13] K. Jain. Factor 2 approximation algorithm for the generalized Steiner network problem. In Proceedings of the 39th annual IEEE Foundations of Computer Science, pages 448–457, 1998. [14] M. Kapinski and A. Zelikovsky. New approximation algorithms for the Steiner tree problem. Journal of Combinatorial Optimization, 1:47–65, 1997. [15] R. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. R.E Miller and J.W. Thatcher, 1972. [16] G. Kortsarz, R. Krauthgamer, and J. R. Lee. Hardness of approximation for vertexconnectivity network-design problems. Approximation Algorithms for Combinatorial Optimization, 2462:185–199, 2002. [17] X. Li, F. Zou, Y. Huang, D. Kim, and W. Wu. A better constant-factor approximation for selected-internal Steiner minimum tree. In Proceedings of the 14th Annual International Conference on Computing and Combinatorics, pages 568–576, 2008. [18] H. Prommel and A. Steger. RNC-approximation algorithms for the Steiner problems. In Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science,pages 559–570, 1997. [19] R. Ravi and D. P. Williamson. An approximation algorithm for minimum-cost vertexconnectivity problems. Algorithmica, 18:21–43, 1997. [20] G. Robins and A. Zelikovsky. Improved Steiner tree approximation in graphs. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770–779, 2000. [21] H. Takahashi and A. Matsuyama. An approximate solution for the Steiner problem in graphs. Mathematica Japonica, 6:573–577, 1980. [22] A. Zelikovsky. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica, 9:463–470, 1993. [23] A. Zelikovsky. Better approximation bounds for the network and Euclidean Steiner tree problems. Technical report, CS-96-06, University of Virginia, 1996. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43741 | - |
dc.description.abstract | 給定一個完全圖G跟一些不相交的點集R={R1,R2,...,Rk},內部史坦納森林的問題就是找一個總重量最輕的史坦納森林,而且在這史坦納森林裡每個點集內的點都要求相互連接且每個R點都不是葉子。若ρ'是史坦納森林問題的一個近似解,m是史坦納森林的連接組件(connected component)的數量,則我們針對內部史坦納森林的問題給予一個2ρ'+4logm的近似解。若k=1,這問題就是內部史坦納樹的問題。ρ是史坦納樹問題的近似解而且之前最好的結果是2ρ+1,我們則給予一個新的近似解2ρ。
此外,如果我們允許最後的圖可能會有循環(cycle)在裡面,也就是不再要求是樹或森林,我們就稱呼這問題是內部史坦納子圖的問題,而且同樣地也給予一個近似解的答案。 | zh_TW |
dc.description.abstract | Given a complete graph G = (V,E) with metric weight function c : E → R+ and a list R = {R1,R2, ...,Rk} of disjoint vertex subset of V , an internal Steiner forest problem is seek a Steiner forest such that the vertices in Ri are connected with each other and restricted to be internal vertex for this forest. Suppose ρ′ is the approximation ratio for the Steiner forest problem, and m is the number of connected component. we give a approximation ratio 2ρ′ + 4 logm for this problem. If k = 1, this problem is an internal Steiner tree problem, due to Hsieh. Suppose ρ is the approximation ratio for the Steiner tree problem, the previous result of an internal Steiner tree problem is 2ρ + 1 and we also obtain an approximation ratio 2ρ. Moreover, if our result graph allow to have cycle in the above problem, we address this case as internal Steiner subgraph problem and also give an approximation ratio. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T02:27:22Z (GMT). No. of bitstreams: 1 ntu-98-R94944030-1.pdf: 230916 bytes, checksum: 01d9a4562dea14eaa07a5b17e3c59eec (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | Acknowledgements........................i
Chinese Abstract.......................ii English Abstract......................iii 1 Introduction................................1 2 Internal Steiner Tree Problem...............4 2.1 Proving Theorem 1.1...................4 3 Internal Steiner Forest Problem.............6 3.1 Proving Theorem 1.2...................7 4 Internal Steiner Subgraph Problem..........10 4.1 Proving Theorem 1.3..................10 Bibliography 12 | |
dc.language.iso | en | |
dc.title | 內部史坦納森林之近似演算 | zh_TW |
dc.title | Approximating Internal Steiner Forest | en |
dc.type | Thesis | |
dc.date.schoolyear | 97-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 高明達,何錦文 | |
dc.subject.keyword | 史坦納樹,史坦納森林, | zh_TW |
dc.subject.keyword | Steiner tree,Steiner forest, | en |
dc.relation.page | 14 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2009-08-17 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
Appears in Collections: | 資訊網路與多媒體研究所 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-98-1.pdf Restricted Access | 225.5 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.