{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T12:54:58Z","timestamp":1773752098160,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540327554","type":"print"},{"value":"9783540327561","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11682462_39","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T06:50:30Z","timestamp":1140159030000},"page":"410-422","source":"Crossref","is-referenced-by-count":3,"title":["Network Flow Spanners"],"prefix":"10.1007","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenyu","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom.\u00a09, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"39_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/3-540-45061-0_32","volume-title":"Automata, Languages and Programming","author":"S. Baswana","year":"2003","unstructured":"Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k \u22121)- spanner of o(n1+1\/k) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 384\u2013396. Springer, Heidelberg (2003)"},{"key":"39_CR3","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L. Cai","year":"1995","unstructured":"Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Discr. Math.\u00a08, 359\u2013387 (1995)","journal-title":"SIAM J. Discr. Math."},{"key":"39_CR4","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1137\/S009753979833920X","volume":"30","author":"J. Cheriyan","year":"2000","unstructured":"Cheriyan, J., Thurimella, R.: Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching. SIAM J. Comput.\u00a030, 528\u2013560 (2000)","journal-title":"SIAM J. Comput."},{"key":"39_CR5","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"L.P. Chew","year":"1989","unstructured":"Chew, L.P.: There are planar graphs almost as good as the complete graph. J. of Computer and System Sciences\u00a039, 205\u2013219 (1989)","journal-title":"J. of Computer and System Sciences"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Elkin, M., Peleg, D.: (1 + \u03b5, \u03b2)-spanner constructions for general graphs. In: STOC 2001, pp. 173\u2013182 (2001)","DOI":"10.1145\/380752.380797"},{"key":"39_CR7","unstructured":"Emek, Y., Peleg, D.: Approximating Minimum Max-Stretch spanning Trees on unweighted graphs. In: SODA 2004, pp. 261\u2013270 (2004)"},{"key":"39_CR8","doi-asserted-by":"crossref","unstructured":"Even, G., Kortsarz, G., Slany, W.: On network design problems: fixed cost flows and the Covering Steiner Problem. Transactions on Algorithms (to appear)","DOI":"10.1007\/3-540-45471-3_33"},{"key":"39_CR9","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/jagm.1998.0931","volume":"28","author":"C.G. Fernandes","year":"1998","unstructured":"Fernandes, C.G.: A Better Approximation Ratio for the Minimum Size k-Edge-Connected Spanning Subgraph Problem. J. Algorithms\u00a028, 105\u2013124 (1998)","journal-title":"J. Algorithms"},{"key":"39_CR10","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"G.N. Frederickson","year":"1981","unstructured":"Frederickson, G.N., J\u00e1J\u00e1, J.: Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing\u00a010, 270\u2013283 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"39_CR11","unstructured":"Gabow, H.N., Goemans, M.X., Tardos, E., Williamson, D.P.: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. In: SODA 2005, pp. 562\u2013571 (2005)"},{"key":"39_CR12","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. Program.\u00a082, 13\u201340 (1998)","journal-title":"Math. Program."},{"key":"39_CR13","unstructured":"Goemans, M.X., Goldberg, A.V., Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9., Williamson, D.P.: Improved Approximation Algorithms for Network Design Problems. In: SODA 1994, pp. 223\u2013232 (1994)"},{"key":"39_CR14","first-page":"551","volume":"9","author":"R.E. Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. SIAM\u00a09, 551\u2013570 (1961)","journal-title":"J. SIAM"},{"key":"39_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/3-540-45753-4_16","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"R. Hassin","year":"2002","unstructured":"Hassin, R., Levin, A.: Minimum restricted diameter spanning trees. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 175\u2013184. Springer, Heidelberg (2002)"},{"key":"39_CR16","doi-asserted-by":"crossref","unstructured":"Khuller, S., Vishkin, U.: Biconnectivity Approximations and Graph Carvings. In: STOC 1992, pp. 759\u2013770 (1992)","DOI":"10.1145\/129712.129786"},{"key":"39_CR17","volume-title":"OR 1998","author":"S.O. Krumke","year":"1998","unstructured":"Krumke, S.O., Noltemeier, H., Schwarz, S., Wirth, H.-C., Ravi, R.: Flow Improvement and Network Flows with Fixed Costs. In: OR 1998. Springer, Heidelberg (1998), ftp:\/\/www.mathematik.uni-kl.de\/pub\/scripts\/krumke\/or98-flow.pdf"},{"key":"39_CR18","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/net.3230230417","volume":"23","author":"A.L. Liestman","year":"1993","unstructured":"Liestman, A.L., Shermer, T.: Additive graph spanners. Networks\u00a023, 343\u2013364 (1993)","journal-title":"Networks"},{"key":"39_CR19","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A Linear-Time Algorithm for Finding a Sparse k- Connected Spanning Subgraph of a k-Connected Graph. Algorithmica\u00a07, 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"39_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph Spanners. J. Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. In: Proc. 6th ACM SPDC, Vancouver, pp. 77\u201385 (1987)","DOI":"10.1145\/41840.41847"},{"key":"39_CR22","doi-asserted-by":"crossref","unstructured":"Peleg, D., Upfal, E.: A tradeoff between space and efficiency for routing tables. In: STOC 1998, pp. 43\u201352 (1988)","DOI":"10.1145\/62212.62217"},{"key":"39_CR23","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: SODA 2000, pp. 770\u2013779 (2000)"},{"key":"39_CR24","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Goemans, M.X., Mihail, M., Vazirani, V.V.: A primal-dual approximation algorithm for generalized Steiner network problems. STOC 1993, pp. 708\u2013717 (1993)","DOI":"10.1145\/167088.167268"}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T20:18:37Z","timestamp":1555445917000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11682462_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}