{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:33:19Z","timestamp":1743111199792,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":94,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642022494"},{"type":"electronic","value":"9783642022500"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02250-0_1","type":"book-chapter","created":{"date-parts":[[2009,11,17]],"date-time":"2009-11-17T11:17:06Z","timestamp":1258456626000},"page":"1-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Graphs and Algorithms in Communication Networks on Seven League Boots"],"prefix":"10.1007","author":[{"given":"Arie M. C. A.","family":"Koster","sequence":"first","affiliation":[]},{"given":"Xavier","family":"Mu\u00f1oz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,11,9]]},"reference":[{"issue":"1","key":"1_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1111\/j.1467-9574.1996.tb01478.x","volume":"50","author":"K. I. Aardal","year":"1996","unstructured":"Aardal, K. I., Hoesel, C. P. M. v.: Polyhedral techniques in combinatorial optimization I: theory. Statistica Neerlandica 50(1), 3\u201326 (1996)","journal-title":"Statistica Neerlandica"},{"issue":"2","key":"1_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1111\/1467-9574.00104","volume":"53","author":"K. I. Aardal","year":"1999","unstructured":"Aardal, K. I., Hoesel, C. P. M. v.: Polyhedral techniques in combinatorial optimization II: applications and computations. Statistica Neerlandica 53(2), 131\u2013177 (1999)","journal-title":"Statistica Neerlandica"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Aardal, K. I., Hoesel, C. P. M. v., Koster, A. M. C. A., Mannino, C., Sassano, A.: Models and solution techniques for the frequency assignment problem. Annals of Operations Research 153, 79\u2013129 (2007). URL http:\/\/dx.doi.org\/10.1007\/s10479-007-0178-0","DOI":"10.1007\/s10479-007-0178-0"},{"volume-title":"Local Search in Combinatorial Optimization","year":"1997","key":"1_CR4","unstructured":"Aarts, E. H. L., Lenstra, J. K. (eds.): Local Search in Combinatorial Optimization. Wiley, Chichester (1997)"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Achterberg, T.: SCIP: solving constraint integer programs. Mathematical Programming Computation 1(1), 1\u201341 (2009). URL http:\/\/scip.zib.de\/","DOI":"10.1007\/s12532-008-0001-1"},{"key":"1_CR6","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 Journal on Computing 24, 440\u2013456 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"1_CR7","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R. K. Ahuja","year":"1993","unstructured":"Ahuja, R. K., Magnanti, T. L., Orlin, J. B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New Jersey (1993)"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer-Verlag (1999)","DOI":"10.1007\/978-3-642-58412-1"},{"key":"1_CR9","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2 edn. Springer-Verlag (2008). http:\/\/www.cs.rhul.ac.uk\/books\/dbook\/"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree bounded directed network design. In: Proceedings of the 40th annual ACM symposium on Theory of computing, STOC 2008, pp. 769\u2013778 (2008)","DOI":"10.1145\/1374376.1374486"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1287\/opre.48.2.318.12378","volume":"48","author":"C. Barnhart","year":"2000","unstructured":"Barnhart, C., Hane, C. A., Vance, P. H.: Using branch-and-price-and-cut to origin-destination integer multi-commodity flow problems. Operations Research 48, 318\u2013326 (2000)","journal-title":"Operations Research"},{"key":"1_CR12","unstructured":"Bazaraa, M. S., Shetty, C. M.: Nonlinear programming: Theory and algorithms. John Wiley & Sons (1979)"},{"issue":"2","key":"1_CR13","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"L. A. Belady","year":"1966","unstructured":"Belady, L. A.: A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal 5(2), 78\u2013101 (1966)","journal-title":"IBM Systems Journal"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, pcps and non-approximability \u2013 towards tight results. SIAM Journal on Computing 27, 804\u2013915 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF01788663","volume":"5","author":"J. C. Bermond","year":"1989","unstructured":"Bermond, J. C., Delorme, C., Quisquater, J. J.: Strategies for interconnection networks: some methods from graph theory. Graphs and Combinatorics 5, 107\u2013123 (1989)","journal-title":"Graphs and Combinatorics"},{"key":"1_CR16","unstructured":"Bertsekas, D. P.: Nonlinear Programming, 2nd edn. Athena Scientific (1999)"},{"key":"1_CR17","unstructured":"Bhandari, R.: Survivable Networks: Algorithms for Diverse Routing. Kluwer Academic Publishers (1999)"},{"key":"1_CR18","unstructured":"Bienstock, D., Bley, A.: Capacitated network design with mulicast commodities. In: Proceedings of 8th International Conference on Telecommunication Systems. Nashville, TN (2000). URL http:\/\/www.zib.de\/Publications\/abstracts\/ZR-00-14\/"},{"key":"1_CR19","first-page":"177","volume":"81","author":"D. Bienstock","year":"1998","unstructured":"Bienstock, D., Chopra, S., G\u00fcnl\u00fck, O., Tsai, C. Y.: Minimum cost capacity installation for multicommodity network flows. Mathematical Programming 81, 177\u2013199 (1998)","journal-title":"Mathematical Programming"},{"issue":"1","key":"1_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1287\/opre.50.1.3.17780","volume":"50","author":"R. Bixby","year":"2002","unstructured":"Bixby, R.: Solving real-world linear programs: A decade and more of progress. Operations Research 50(1), 3\u201315 (2002)","journal-title":"Operations Research"},{"key":"1_CR21","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/1.9780898718805.ch18","volume-title":"The Sharpest Cut: The Impact of Manfred Padberg and His Work","author":"R. E. Bixby","year":"2004","unstructured":"Bixby, R. E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mixed-Integer Programming: A Progress Report. In: M. Gr\u00f6tschel (ed.) The Sharpest Cut: The Impact of Manfred Padberg and His Work, MPS-SIAM Series on Optimization, vol. 4, pp. 309\u2013326. SIAM (2004)"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. North-Holland (1976). http:\/\/www.ecp6.jussieu.fr\/pageperso\/bondy\/books\/gtwa\/gtwa.html","DOI":"10.1007\/978-1-349-03521-2"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1023\/A:1018908907763","volume":"76","author":"R. Bornd\u00f6rfer","year":"1998","unstructured":"Bornd\u00f6rfer, R., Eisenbl\u00e4tter, A., Gr\u00f6tschel, M., Martin, A.: Frequency assignment in cellular phone networks. Annals of Operations Research 76, 73\u201394 (1998)","journal-title":"Annals of Operations Research"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D. Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz, D.: New methods to color the vertices of a graph. Communications of the ACM 22, 251\u2013256 (1979)","journal-title":"Communications of the ACM"},{"key":"1_CR25","unstructured":"Chartrand, G., Lesniak, L.: Graphs & Digraphs. Wadsworth & Brooks (1986)"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Chopra, S., Gilboa, I., Sastry, S.: Source sink flows with capacity installation in batches. DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 85 (1998)","DOI":"10.1016\/S0166-218X(98)00024-9"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01582573","volume":"64","author":"S. Chopra","year":"1994","unstructured":"Chopra, S., Rao, M. R.: The Steiner tree problem I: Formulations, compositions and extension of facets. Mathematical Programming 64, 209\u2013229 (1994)","journal-title":"Mathematical Programming"},{"key":"1_CR28","first-page":"244","volume":"33","author":"F. R. K. Chung","year":"1987","unstructured":"Chung, F. R. K., Coffman, E. G., Reiman, M. I., Simon, B.: On the capacity and forwarding index of communication networks. IEEE Trans. on Information Theory 33, 244\u2013232 (1987)","journal-title":"IEEE Trans. on Information Theory"},{"key":"1_CR29","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Linear Programming. W. H. Freeman and Company, New York (1983)"},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"Clos, C.: A study of non-blocking switching networks. Bell System Technical Journal (1953)","DOI":"10.1002\/j.1538-7305.1953.tb01433.x"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Cook, W.: Fifty-plus years of combinatorial integer programming (2009). URL http:\/\/www2.isye.gatech.edu\/ wcook\/ip50\/ip50.pdf","DOI":"10.1007\/978-3-540-68279-0_12"},{"key":"1_CR32","unstructured":"Cook, W. J., Cunningham, W. H., Pulleybank, W. R., Schrijver, A.: Combinatorial Optimization. Series in Discrete Mathematics and Optimization. Wiley-Interscience (1998)"},{"key":"1_CR33","unstructured":"Cost action 293 \u2013 graphs and algorithms in communication networks. http:\/\/www.cost293.org\/"},{"issue":"12","key":"1_CR34","doi-asserted-by":"publisher","first-page":"2076","DOI":"10.1109\/50.908818","volume":"18","author":"D. Coudert","year":"2000","unstructured":"Coudert, D., Ferreira, A., Mu\u00f1oz, X.: A multihop-multi-OPS optical interconnection network. IEEE\/OSA Journal of Lightwave Technology 18(12), 2076\u20132085 (2000)","journal-title":"IEEE\/OSA Journal of Lightwave Technology"},{"key":"1_CR35","unstructured":"Coudert, D., Mu\u00f1oz, X.: Graph theory and traffic grooming in WDM rings. In: Recent Research Developments in Optics, 3, chap. 37, pp. 759\u2013778. Research Signpost. Kerala, India (2003)"},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Dantzig, G. B.: Linear Programming and Extensions. Princeton University Press (1998). Originally published in 1963","DOI":"10.7249\/R366"},{"key":"1_CR37","first-page":"215","volume-title":"Linear Inequalities and Related Systems, Annals of Mathematics Series","author":"G. B. Dantzig","year":"1956","unstructured":"Dantzig, G. B., Fulkerson, D. R.: On the max-flow min-cut theorem of networks. In: H. W. Kuhn, A. W. Tucker (eds.) Linear Inequalities and Related Systems, Annals of Mathematics Series, vol. 38, pp. 215\u2013221. Princeton University Press, Princeton, New Jersey (1956)"},{"key":"1_CR38","unstructured":"Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173, 3 edn. Springer-Verlag, Heidelberg (2005). http:\/\/www.math.uni-hamburg.de\/home\/diestel\/books\/graph.theory\/"},{"key":"1_CR39","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"Dijkstra, E. W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"key":"1_CR40","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/0890-5401(87)90031-9","volume":"72","author":"D. Dolev","year":"1987","unstructured":"Dolev, D., Halpern, J., Simons, B., Strong, H.: A new look at fault tolerant network routing. Information and Computation 72, 180\u2013196 (1987)","journal-title":"Information and Computation"},{"key":"1_CR41","volume-title":"Frequency assignment in GSM networks: Models, heuristics, and lower bounds","author":"A. Eisenbl\u00e4tter","year":"2001","unstructured":"Eisenbl\u00e4tter, A.: Frequency assignment in GSM networks: Models, heuristics, and lower bounds. Ph.D. thesis, Technische Universit\u00e4t Berlin, Berlin, Germany (2001)"},{"key":"1_CR42","first-page":"273","volume-title":"Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO\u201902), Lecture Notes in Computer Science","author":"A. Eisenbl\u00e4tter","year":"2002","unstructured":"Eisenbl\u00e4tter, A.: The semidefinite relaxation of the k-partition polytope is strong. In: W. J. Cook, A. S. Schulz (eds.) Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO\u201902), Lecture Notes in Computer Science, vol. 2337, pp. 273\u2013290. Springer-Verlag, Berlin Heidelberg (2002)"},{"issue":"1","key":"1_CR43","doi-asserted-by":"crossref","first-page":"51","DOI":"10.7151\/dmgt.1158","volume":"22","author":"A. Eisenbl\u00e4tter","year":"2002","unstructured":"Eisenbl\u00e4tter, A., Gr\u00f6tschel, M., Koster, A. M. C. A.: Frequency planning and ramifications of coloring. Discussiones Mathematicae Graph Theory 22(1), 51\u201388 (2002)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"1_CR44","unstructured":"Eisenbl\u00e4tter, A., Koster, A. M. C. A.: FAP web \u2013 A website devoted to frequency assignment. URL: http:\/\/fap.zib.de (2000\u20132008)"},{"key":"1_CR45","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1002\/jgt.3190130603","volume":"13","author":"J. F\u00e0brega","year":"1989","unstructured":"F\u00e0brega, J., Fiol, M. A.: Maximally connected digraphs. Journal of Graph Theory 13, 657\u2013668 (1989)","journal-title":"Journal of Graph Theory"},{"key":"1_CR46","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1023\/A:1026158611840","volume":"24","author":"A. Ferreira","year":"2003","unstructured":"Ferreira, A., P\u00e9rennes, S., Richa, A. W., Rivano, H., Moses, N. S.: Models, Complexity and Algorithms for the Design of Multifiber WDM Networks. Telecommunication Systems 24, 123\u2013138 (2003)","journal-title":"Telecommunication Systems"},{"issue":"4","key":"1_CR47","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A. Fiat","year":"1991","unstructured":"Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., Young, N. E.: Competitive paging algorithms. Journal of Algorithms 12(4), 685\u2013699 (1991)","journal-title":"Journal of Algorithms"},{"key":"1_CR48","unstructured":"Fortz, B., Labb\u00e9, M.: Design of survivable networks. In: M. G. C. Resende, P. M. Pardalos (eds.) Handbook of Optimization in Telecommunications, chap. 15, pp. 367\u2013389. Springer (2006)"},{"key":"1_CR49","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M. R. Garey","year":"1977","unstructured":"Garey, M. R., Johnson, D. S.: The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics 32, 826\u2013834 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"1_CR50","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., Johnson, D. S.: Computers and intractability: a guide to the theory of NP-completeness. Freeman and Company, N. Y. (1979)"},{"key":"1_CR51","doi-asserted-by":"crossref","unstructured":"Goemans, M. X.: Minimum bounded degree spanning trees. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pp. 273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"key":"1_CR52","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Krumke, S. O., Rambau, J. (eds.): Online Optimization of Large Scale Systems. Springer (2001)","DOI":"10.1007\/978-3-662-04331-8"},{"key":"1_CR53","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"1_CR54","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02579139","volume":"4","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Corrigendum to our paper \u201cthe ellipsoid method and its consequences in combinatorial optimization\u201d. Combinatorica 4, 291\u2013295 (1984)","journal-title":"Combinatorica"},{"key":"1_CR55","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. No. 2 in Algorithms and Combinatorics. Springer-Verlag (1988)","DOI":"10.1007\/978-3-642-97881-4"},{"issue":"3","key":"1_CR56","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1137\/0802024","volume":"2","author":"M. Gr\u00f6tschel","year":"1992","unstructured":"Gr\u00f6tschel, M., Monma, C. L., Stoer, M.: Facets for polyhedra arising in the design of communication networks with low-connectivity constraints. SIAM Journal on Optimization 2(3), 474\u2013504 (1992)","journal-title":"SIAM Journal on Optimization"},{"key":"1_CR57","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/S0927-0507(05)80127-6","volume-title":"Network Models","author":"M. Gr\u00f6tschel","year":"1995","unstructured":"Gr\u00f6tschel, M., Monma, C. L., Stoer, M.: Design of Survivable Networks. In: M. O. Ball, T. L. Magnanti, C. L. Monma, G. L. Nemhauser (eds.) Network Models, Handbooks in Operations Research and Management Science, vol. 7, pp. 617\u2013672. North-Holland (1995)"},{"issue":"6","key":"1_CR58","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1287\/opre.43.6.1012","volume":"43","author":"M. Gr\u00f6tschel","year":"1995","unstructured":"Gr\u00f6tschel, M., Monma, C. L., Stoer, M.: Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements. Operations Research 43(6), 1012\u20131024 (1995)","journal-title":"Operations Research"},{"key":"1_CR59","volume-title":"Mesh-based Survivable Networks: Options and Strategies for Optical, MPLS","author":"W. D. Grover","year":"2003","unstructured":"Grover, W. D.: Mesh-based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking. Prentice Hall (2003)"},{"key":"1_CR60","doi-asserted-by":"crossref","unstructured":"Henningsson, M., Holmberg, K., Yuan, D.: Ring network design. In: M. G. C. Resende, P. M. Pardalos (eds.) Handbook of Optimization in Telecommunications, chap. 12, pp. 291\u2013311. Springer (2006)","DOI":"10.1007\/978-0-387-30165-5_12"},{"key":"1_CR61","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0166-218X(89)90022-X","volume":"23","author":"M. C. Heydemann","year":"1989","unstructured":"Heydemann, M. C., Meyer, J. C., Sotteau, D.: On forwarding indices of networks. Discrete Applied Mathematics 23, 103\u2013123 (1989)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"1_CR62","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1016\/S0377-2217(98)00008-3","volume":"113","author":"K. Holmberg","year":"1999","unstructured":"Holmberg, K., R\u00f6nnqvist, M., Yuan, D.: An exact algorithm for the capacitated facility location problems with single sourcing. European Journal of Operational Research 113(3), 544\u2013559 (1999)","journal-title":"European Journal of Operational Research"},{"key":"1_CR63","doi-asserted-by":"crossref","unstructured":"Hromkovic, J., Klasing, R., Monien, B., Peine, R.: Dissemination of information in interconnection networks (broadcasting and gossiping) (1996)","DOI":"10.1007\/978-1-4757-2491-2_5"},{"key":"1_CR64","unstructured":"ILOG: CPLEX version 11.1 (2008). http:\/\/www.ilog.com\/products\/cplex"},{"issue":"4","key":"1_CR65","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"1_CR66","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"Karp, R. M.: Reducibility among combinatorial problems. In: R. E. Miller, J. W. Thatcher (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"1_CR67","first-page":"159","volume-title":"Inequalities","author":"V. Klee","year":"1972","unstructured":"Klee, V., Minty, G. J.: How good is the Simplex algorithm? In: O. Shisha (ed.) Inequalities, III, pp. 159\u2013175. Academic Press, New York, NY (1972)"},{"key":"1_CR68","unstructured":"Koch, T., Martin, A., Vo\u00df, S.: SteinLib: An updated library on Steiner tree problems in graphs. Tech. Rep. ZIB-Report 00-37, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin, Takustr. 7, Berlin (2000). URL http:\/\/elib.zib.de\/steinlib"},{"key":"1_CR69","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J. B. Kruskal Jr","year":"1956","unstructured":"Kruskal Jr., J. B.: On the shortest spanning tree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7, 48\u201350 (1956)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"1_CR70","unstructured":"LEMON: A C++ Library for Efficient Modelling and Optimization in Networks. http:\/\/lemon.cs.elte.hu"},{"key":"1_CR71","unstructured":"Lindberg, P.: Network optimisation with successive smooth approximation. In: 11th Nordic Teletraffic Seminar. Stockholm (1993)"},{"key":"1_CR72","unstructured":"Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers (1996)"},{"issue":"13","key":"1_CR73","doi-asserted-by":"publisher","first-page":"1083","DOI":"10.1364\/OL.18.001083","volume":"18","author":"G. Marsden","year":"1993","unstructured":"Marsden, G., Marchand, P., Harvey, P., Esener, S.: Optical transpose interconnection system architectures. OSA Optics Letters 18(13), 1083\u20131085 (1993)","journal-title":"OSA Optics Letters"},{"key":"1_CR74","unstructured":"Martello, S., Toth, P.: Knapsack Problems \u2013 Algorithms and Computer Implementations. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons (1990). URL http:\/\/www.or.deis.unibo.it\/kp.html"},{"key":"1_CR75","unstructured":"Metzger, B. H.: Spectrum management technique (Fall 1970). Presentation at 38th National ORSA meeting (Detroit, MI)"},{"key":"1_CR76","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"G. L. Nemhauser","year":"1988","unstructured":"Nemhauser, G. L., Wolsey, L. A.: Integer and Combinatorial Optimization. Wiley, N. Y. (1988)"},{"key":"1_CR77","unstructured":"Orlowski, S., Pi\u00f3ro, M., Tomaszewski, A., Wess\u00e4ly, R.: SNDlib 1.0\u2013Survivable Network Design Library. In: Proceedings of International Network Optimization Conference (INOC2007) (2007). http:\/\/sndlib.zib.de"},{"key":"1_CR78","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing \u2013 A Locality-Sensitive Approach. Monographs in Discrete Mathematics and Applications. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"1_CR79","doi-asserted-by":"crossref","unstructured":"Pi\u00f3ro, M., Medhi, D.: Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann (2004)","DOI":"10.1016\/B978-012557189-0\/50011-1"},{"key":"1_CR80","unstructured":"Polzin, T.: Algorithms for the Steiner problem in networks. Ph.D. thesis, Universit\u00e4t des Saarlandes (2003)"},{"key":"1_CR81","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R. C. Prim","year":"1957","unstructured":"Prim, R. C.: Shortest connection networks and some generalizations. The Bell System Technical Journal 36, 1389\u20131401 (1957)","journal-title":"The Bell System Technical Journal"},{"key":"1_CR82","volume-title":"Theory of linear and integer programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of linear and integer programming. Wiley, New York (1986)"},{"key":"1_CR83","unstructured":"Schrijver, A.: Combinatorial Optimization \u2013 Polyhedra and Efficiency. No. 24 in Algorithms and Combinatorics. Springer (2003)"},{"issue":"2","key":"1_CR84","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1985","unstructured":"Sleator, D. D., Tarjan, R. E.: Amortized efficiency of list update and paging rules. Communications of the ACM 28(2), 202\u2013208 (1985)","journal-title":"Communications of the ACM"},{"key":"1_CR85","unstructured":"Stidsen, T., Petersen, B., Rasmussen, K. B., Spoorendonk, S., Zachariasen, M., Rambach, F., Kiese, M.: Optimal routing with single backup path protection. In: Proceedings International Network Optimization Conference (INOC 2007). Spa, Belgium (2007)"},{"issue":"2","key":"1_CR86","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1002\/net.3230040204","volume":"4","author":"J. W. Suurballe","year":"1974","unstructured":"Suurballe, J. W.: Disjoint paths in a network. Networks 4(2), 125\u2013145 (1974)","journal-title":"Networks"},{"key":"1_CR87","unstructured":"Tel, G.: Introduction to Distributed Algorithms. Cambridge University Press (1994)"},{"key":"1_CR88","unstructured":"Vanderbei, R. J.: Linear Programming: Foundations and Extensions, International Series in Operations Research & Management Science, vol. 114, 3 edn. Springer-Verlag (2008)"},{"key":"1_CR89","doi-asserted-by":"crossref","unstructured":"Vo<s>, S.: Steiner tree problems in telecommunications. In: M. G. C. Resende, P. M. Pardalos (eds.) Handbook of Optimization in Telecommunications, chap. 18, pp. 459\u2013515. Springer (2006)","DOI":"10.1007\/978-0-387-30165-5_18"},{"key":"1_CR90","unstructured":"Wess\u00e4ly, R.: DImensioning Survivable Capacitated NETworks. Ph.D. thesis, Technische Universit\u00e4t Berlin (2000)"},{"key":"1_CR91","unstructured":"West, D. B.: Introduction to Graph Theory, 2 edn. Prentice Hall (2001)"},{"key":"1_CR92","unstructured":"Wolsey, L. A.: Integer Programming. Series in Discrete Mathematics and Optimization. Wiley-Interscience (1998)"},{"key":"1_CR93","volume-title":"Design of survivable optical networks by mathematical optimization","author":"A. Zymolka","year":"2007","unstructured":"Zymolka, A.: Design of survivable optical networks by mathematical optimization. Ph.d. thesis, TU Berlin (2007)"},{"key":"1_CR94","unstructured":"Zymolka, A., Koster, A. M. C. A., Wess\u00e4ly, R.: Transparent optical network design with sparse wavelength conversion. In: Proceedings of ONDM 2003, pp. 61\u201380. The 7th IFIP Working Conference on Optical Network Design & Modelling, Budapest, Hungary (2003)"}],"container-title":["Texts in Theoretical Computer Science. An EATCS Series","Graphs and Algorithms in Communication Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02250-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,17]],"date-time":"2024-03-17T17:59:27Z","timestamp":1710698367000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-02250-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642022494","9783642022500"],"references-count":94,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02250-0_1","relation":{},"ISSN":["1862-4499"],"issn-type":[{"type":"print","value":"1862-4499"}],"subject":[],"published":{"date-parts":[[2009]]},"assertion":[{"value":"9 November 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}