{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:44:06Z","timestamp":1778294646800,"version":"3.51.4"},"publisher-location":"Boston, MA","reference-count":31,"publisher":"Springer US","isbn-type":[{"value":"9780387306629","type":"print"},{"value":"9780387301655","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-0-387-30165-5_19","type":"book-chapter","created":{"date-parts":[[2008,12,9]],"date-time":"2008-12-09T12:26:59Z","timestamp":1228825619000},"page":"493-515","source":"Crossref","is-referenced-by-count":33,"title":["On Formulations and Methods for the Hop-Constrained Minimum Spanning Tree Problem"],"prefix":"10.1007","author":[{"given":"Geir","family":"Dahl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luis","family":"Gouveia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristina","family":"Requejo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","unstructured":"N. R. Achuthan, L. Caccetta, P. Caccetta, and J. F. Geelen. Algorithms for the minimum weight spanning tree with bounded diameter problem. In et al. P. H. Phua, editor, Optimization Techniques and Applications, volume 1, pages 297\u2013304. World Scientific, 1992."},{"key":"19_CR2","unstructured":"R. Ahuja, T. Magnanti, and J. Orlin. Network flows: Theory, algorithms and applications. Prentice Hall, 1993."},{"key":"19_CR3","unstructured":"D. Alevras, M. Gr\u00f6tschel, and R. Wessaly. A network dimensioning tool. Technical Report SC 96-49, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik, 1996."},{"key":"19_CR4","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1287\/ijoc.4.2.192","volume":"4","author":"A. Balakrishnan","year":"1992","unstructured":"A. Balakrishnan and K. Altinkemer. Using a hop-constrained model to generate alternative communication network design. ORSA Journal on Computing, 4:192\u2013205, 1992.","journal-title":"ORSA Journal on Computing"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/net.3230140112","volume":"14","author":"J. Beasley","year":"1984","unstructured":"J. Beasley. An algorithm for the Steiner problem in graphs. Networks, 14:147\u2013159, 1984.","journal-title":"Networks"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0166-218X(00)00310-3","volume":"112","author":"T. Crainic","year":"2001","unstructured":"T. Crainic, A. Frangioni, and B. Gendron. Bundle-based relaxation methods for multicommodity capacitated fixed charge network design problems. Discrete Applied Mathematics, 112:73\u201399, 2001.","journal-title":"Discrete Applied Mathematics"},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0167-6377(98)00029-7","volume":"23","author":"G. Dahl","year":"1998","unstructured":"G. Dahl. \u201cThe 2-hop spanning tree problem. Operations Research Letters, 23:21\u201326, 1998.","journal-title":"Operations Research Letters"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0167-6377(99)00025-5","volume":"25","author":"G. Dahl","year":"1999","unstructured":"G. Dahl. Notes on polyhedra associated with hop-constrained paths. Operations Research Letters, 25:97\u2013100, 1999.","journal-title":"Operations Research Letters"},{"key":"19_CR9","unstructured":"Dahl G., N. Foldnes, and L. Gouveia. A note on hop-constrained walk polytopes. Technical Report 1\/2003, Centro de Investiga\u00e7\u00e3o Operacional, Faculdade de Ci\u00eancias da Universidade de Lisboa, 2003."},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Dahl G. and L. Gouveia. On the directed hop-constrained shortest path problem. Operations Research Letters, 2003. To appear.","DOI":"10.1016\/S0167-6377(03)00026-9"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"1247","DOI":"10.1109\/TCOM.1985.1096250","volume":"COM-33","author":"B. Gavish","year":"1985","unstructured":"B. Gavish. Augmented Lagrangean based algorithms for centralized network design. IEEE Transactions on Communications, COM-33:1247\u20131257, 1985.","journal-title":"IEEE Transactions on Communications"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"B. Gendron, T. Crainic, and A. Frangioni. Multicommodity capacitated network design. In B Sans\u00f2 and P. Soriano, editors, Telecommunications network planning. Kluwer Academic Publishers, 1999.","DOI":"10.1007\/978-1-4615-5087-7_1"},{"key":"19_CR13","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BFb0120690","volume":"2","author":"A. Geoffrion","year":"1974","unstructured":"A. Geoffrion. Lagrangian relaxation for integer programming. Mathematical Programming Study, 2:82\u2013114, 1974.","journal-title":"Mathematical Programming Study"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01582064","volume":"63","author":"M. Goemans","year":"1994","unstructured":"M. Goemans. The Steiner polytope and related polyhedra. Mathematical Programming, 63:157\u2013182, 1994.","journal-title":"Mathematical Programming"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1016\/0305-0548(94)00074-I","volume":"22","author":"L. Gouveia","year":"1995","unstructured":"L. Gouveia. Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints. Computers and Operations Research, 22: 959\u2013970, 1995.","journal-title":"Computers and Operations Research"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/0377-2217(95)00090-9","volume":"95","author":"L. Gouveia","year":"1996","unstructured":"L. Gouveia. Multicommodity flow models for spanning trees with hop constraints. European Journal of Operational Research, 95:178\u2013190, 1996.","journal-title":"European Journal of Operational Research"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/ijoc.10.2.180","volume":"10","author":"L. Gouveia","year":"1998","unstructured":"L. Gouveia. Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS Journal on Computing, 10:180\u2013188, 1998.","journal-title":"INFORMS Journal on Computing"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1002\/net.10069","volume":"41","author":"L. Gouveia","year":"2003","unstructured":"L Gouveia and T. Magnanti. Network flow models for designing diameter constrained spanning and Steiner trees. Networks, 41:159\u2013173, 2003.","journal-title":"Networks"},{"key":"19_CR19","unstructured":"L. Gouveia, P. Patr\u00edcio, A. e Sousa, and Valadas R. MPLS over WDM network design with packet level QoS constraints based on ILP models. In Proceedings of IEEE INFOCOM 2003, April 2003."},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/S0377-2217(00)00143-0","volume":"132","author":"L. Gouveia","year":"2001","unstructured":"L. Gouveia and C. Requejo. A new Lagrangian relaxation approach for the hop-constrained minimum spanning tree problem. European Journal of Operational Research, 132:539\u2013552, 2001.","journal-title":"European Journal of Operational Research"},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/BF01580223","volume":"6","author":"M. Held","year":"1974","unstructured":"M. Held, P. Wolfe, and H. Crowder. Validation of subgradient optimization. Mathematical Programming, 6:62\u201388, 1974.","journal-title":"Mathematical Programming"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"K. Holmberg and D. Yuan. A Lagrangean heuristic Based branch-and-Bound approach for the capacitated network design problem. Technical Report LiTH-MAT-R-1996-23, Department of Mathematics, Link\u00f6ping Institute of Technology, 1996.","DOI":"10.1007\/978-3-642-60744-8_15"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1287\/ijoc.11.2.188","volume":"11","author":"L. LeBlanc","year":"1999","unstructured":"L. LeBlanc, J. Chifflet, and P. Mahey. Packet routing in telecommunication networks with path and flow restrictions. INFORMS Journal on Computing, 11:188\u2013197, 1999.","journal-title":"INFORMS Journal on Computing"},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/S0927-0507(05)80126-4","volume":"7","author":"T. Magnanti","year":"1996","unstructured":"T. Magnanti and L. Wolsey. Optimal trees. In Network models, volume 7 of Handbooks in Operations Research and Management Science, pages 503\u2013615. Elsevier, 1996.","journal-title":"Network models"},{"key":"19_CR25","unstructured":"P. Manyem and M. Stallmann. Some approximation results in multicasting. Technical report, North Carolina State University, 1996."},{"key":"19_CR26","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1287\/opre.35.6.820","volume":"35","author":"R. K. Martin","year":"1987","unstructured":"R. K. Martin. Generating alternative mixed-integer programming models using variable redefinition. Operations Research, 35:820\u2013831, 1987.","journal-title":"Operations Research"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"R. K. Martin. Large scale linear and integer optimization: A unified approach. Kluwer Academic Publishers, 1999.","DOI":"10.1007\/978-1-4615-4975-8"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"G. L. Nemhauser and L.A. Wolsey. Integer and combinatorial optimization. John Wiley & Sons, 1988.","DOI":"10.1002\/9781118627372"},{"key":"19_CR29","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/S0377-2217(02)00366-1","volume":"148","author":"H. Pirkul","year":"2003","unstructured":"H. Pirkul and S. Soni. New formulations and solution procedures for the hop constrained network design problem. European Journal of Operational Research, 148: 126\u2013140, 2003.","journal-title":"European Journal of Operational Research"},{"key":"19_CR30","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1023\/A:1018967121276","volume":"86","author":"S. Voss","year":"1999","unstructured":"S. Voss. The Steiner tree problem with hop constraints. Annals of Operations Research, 86:271\u2013294, 1999.","journal-title":"Annals of Operations Research"},{"key":"19_CR31","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0305-0548(88)90033-0","volume":"15","author":"K. Woolston","year":"1988","unstructured":"K. Woolston and S. Albin. The design of centralized networks with reliability and availability constraints. Computers and Operations Research, 15:207\u2013217, 1988.","journal-title":"Computers and Operations Research"}],"container-title":["Handbook of Optimization in Telecommunications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30165-5_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,22]],"date-time":"2023-05-22T19:54:37Z","timestamp":1684785277000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-0-387-30165-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9780387306629","9780387301655"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30165-5_19","relation":{},"subject":[]}}