{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:13:56Z","timestamp":1725484436075},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438663"},{"type":"electronic","value":"9783540454717"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45471-3_20","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T13:18:22Z","timestamp":1179753502000},"page":"190-199","source":"Crossref","is-referenced-by-count":3,"title":["The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms"],"prefix":"10.1007","author":[{"given":"Harold N.","family":"Gabow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0020-0190(98)00010-6","volume":"65","author":"S. Arya","year":"1998","unstructured":"Arya, S., Ramesh, H.: A 2.5-factor approximation algorithm for the k-MST problem. Inf. Proc. Letters 65 (1998) 117\u2013118","journal-title":"Inf. Proc. Letters"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A. Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comp. 24 (1995) 440\u2013456","journal-title":"SIAM J. Comp"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. Proc. 26th Annual ACM Symp. on Theory Comput. (1994) 163\u2013171","DOI":"10.1145\/195058.195125"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/jcss.1997.1542","volume":"58","author":"A. Blum","year":"1999","unstructured":"Blum, A., Ravi, R., Vempala, S.: A constant-factor approximation algorithm for the k-MST problem. J. Comp. Sys. Sci. 58 (1999) 101\u2013108","journal-title":"J. Comp. Sys. Sci."},{"key":"20_CR5","unstructured":"Cole, R., Hariharan, R., Lewenstein, M., Porat, E.: A faster implementation of the Goemans-Williamson clustering algorithm. Proc. 12th Annual ACM-SIAM Symp. on Disc. Alg. (2001) 17\u201325"},{"key":"20_CR6","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. 2nd edn. McGraw-Hill, NY (2001)","edition":"2nd edn"},{"key":"20_CR7","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. Proc. 37th Annual Symp. on Foundations Comp. Sci. (1996) 302\u2013309"},{"key":"20_CR8","unstructured":"Goemans, M., Goldberg, A., Plotkin, S., Shmoys, D., Tardos, E., Williamson, D.: Improved approximation algorithms for network design problems. Proc. 5th Annual ACM-SIAM Symp. on Disc. Alg. (1994) 223\u2013232"},{"key":"20_CR9","first-page":"13","volume":"82","author":"H.N. Gabow","year":"1998","unstructured":"Gabow, H.N., Goemans, M.X., Williamson, D.P.: An efficient approximation algorithm for the survivable network design problem. Math. Programming B 82 (1998) 13\u201340","journal-title":"Math. Programming B"},{"key":"20_CR10","unstructured":"Goemans, M.X., Kleinberg, J.: An improved approximation ratio for the minimum latency problem. Proc. 7th Annual ACM-SIAM Symp. on Disc. Alg. (1996) 152\u2013158"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Pettie, S.: The dynamic vertex minimum problem and its application to clustering-type approximation algorithms. Univ. of Colorado TR# CU-CS-928-02 (2002)","DOI":"10.1007\/3-540-45471-3_20"},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M.X. Goemans","year":"1995","unstructured":"Goemans M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comp. 24 (1995) 296\u2013317","journal-title":"SIAM J. Comp."},{"key":"20_CR13","unstructured":"Goemans M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and its application to network design problems. in Approximation Algorithms for NP-hard Problems, D.S. Hochbaum (ed.) (1997) 144\u2013191"},{"key":"20_CR14","unstructured":"Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: Theory and practice. Proc. 11th Annual ACM-SIAM Symp. on Disc. Alg. (2000) 760\u2013769"},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0020-0190(94)00156-1","volume":"52","author":"P. Klein","year":"1994","unstructured":"Klein, P.: A data structure for bicategories, with application to speeding up an approximation algorithm. Inf. Proc. Letters 52 (1994) 303\u2013307","journal-title":"Inf. Proc. Letters"},{"key":"20_CR16","volume-title":"Algorithms in C++","author":"R. Sedgewick","year":"1998","unstructured":"Sedgewick, R.: Algorithms in C++. 3rd edn. Addison-Wesley, Reading, MA (1998)","edition":"3rd edn."},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Amortized computational complexity. SIAM J. on Algebraic and Discrete Methods 6 (1985) 306\u2013318","journal-title":"SIAM J. on Algebraic and Discrete Methods"},{"key":"20_CR18","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/BF01299747","volume":"15","author":"D.P. Williamson","year":"1995","unstructured":"Williamson, D.P., Goemans M.X., Mihail, M., Vazirani, V.V.: An approximation algorithm for general graph connectivity problems. Combinatorica 15 (1995) 435\u2013454","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45471-3_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T02:42:34Z","timestamp":1556419354000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45471-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438663","9783540454717"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-45471-3_20","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}