{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:45:01Z","timestamp":1743119101723,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602163"},{"type":"electronic","value":"9783540447337"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0030828","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T03:51:40Z","timestamp":1133409100000},"page":"141-150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The multi-weighted spanning tree problem"],"prefix":"10.1007","author":[{"given":"Joseph L.","family":"Ganley","sequence":"first","affiliation":[]},{"given":"Mordecai J.","family":"Golin","sequence":"additional","affiliation":[]},{"given":"Jeffrey S.","family":"Salowe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"unstructured":"M. J. Alexander and G. Robins, \u201cA new approach to FPGA routing based on multiweighted graphs,\u201d ACM\/SIGDA International Workshop on Field-Programmable Gate Arrays (1994).","key":"15_CR1"},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1002\/net.3230070405","volume":"7","author":"R. Chandrasekaran","year":"1977","unstructured":"R. Chandrasekaran, \u201cMinimum ratio spanning trees,\u201d Networks\n7 (1977) 335\u2013342.","journal-title":"Networks"},{"issue":"4","key":"15_CR3","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1137\/0218055","volume":"18","author":"R. Cole","year":"1989","unstructured":"R. Cole, J. S. Salowe, W. L. Steiger, and E. Szemer\u00e9di, \u201cAn optimal-time algorithm for slope selection,\u201d SIAM J. Comput.\n18(4) (1989) 792\u2013810.","journal-title":"SIAM J. Comput."},{"issue":"6","key":"15_CR4","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1109\/43.137519","volume":"11","author":"J. Cong","year":"1992","unstructured":"J. Cong, A. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, \u201cProvably good performance-driven global routing,\u201d IEEE Trans. on CAD\n11(6), (1992), 739\u2013752.","journal-title":"IEEE Trans. on CAD"},{"key":"15_CR5","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0377-2217(86)80007-8","volume":"27","author":"J. R. Current","year":"1986","unstructured":"J. R. Current, C. S. Revelle, and J. L. Cohon, \u201cThe hierarchical network design problem,\u201d Eur. J. Oper. Res.\n27 (1986) 55\u201367.","journal-title":"Eur. J. Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"G. B. Dantzig, W. O. Blattner, and M. R. Rao, \u201cFinding a cycle in a graph with minimum cost to time ratio with application to a ship routing problem\u201d, Theory of Graphs, International Symposium, Gordon and Breach (1967) 77\u201384.","key":"15_CR6","DOI":"10.21236\/AD0646553"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/0377-2217(89)90170-7","volume":"39","author":"C. Duin","year":"1989","unstructured":"C. Duin and T. Volgenant, \u201cReducing the hierarchical network design problem,\u201d Eur. J. Oper. Res.\n39 (1989) 332\u2013344.","journal-title":"Eur. J. Oper. Res."},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/BF02071982","volume":"33","author":"C. Duin","year":"1991","unstructured":"C. Duin and T. Volgenant, \u201cThe multi-weighted Steiner tree problem,\u201d Ann. Oper. Res.\n33 (1991) 451\u2013469.","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"15_CR9","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H. H. Gabow","year":"1986","unstructured":"H. H. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, \u201cEfficient algorithms for finding minimum spanning trees in undirected and directed graphs,\u201d Combinatorica\n6(2) (1986) 109\u2013122.","journal-title":"Combinatorica"},{"unstructured":"M. X. Goemans and D. P. Williamson, \u201cA general approximation technique for constrained forest problems,\u201d Proc. 3rd SODA (1992) 307\u2013316.","key":"15_CR10"},{"unstructured":"M. J. Golin, C. Schwarz, and M. Smid, \u201cFurther Dynamic Computational Geometry\u201d, Proc. Fourth Canad. Conf. Comp. Geom. (1992) 154\u2013159.","key":"15_CR11"},{"unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability, W. H. Freeman (1979).","key":"15_CR12"},{"unstructured":"D. Gusfield, \u201cBounds for the parametric minimum spanning tree problem,\u201d Proc. West Coast Conf. Comb., Graph Theory and Comput., 173\u2013181, 1980.","key":"15_CR13"},{"issue":"3","key":"15_CR14","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1145\/2402.322391","volume":"30","author":"D. Gusfield","year":"1983","unstructured":"D. Gusfield, \u201cParametric combinatorial computing and a problem of program module distribution,\u201d J. ACM\n30(3) (1983) 551\u2013563.","journal-title":"J. ACM"},{"issue":"2","key":"15_CR15","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1287\/moor.14.2.362","volume":"14","author":"R. Hassin","year":"1989","unstructured":"R. Hassin and A. Tamir, \u201cMaximizing classes of two-parameter objectives over matroids,\u201d Math. Oper. Res.\n14(2) (1989) 362\u2013375.","journal-title":"Math. Oper. Res."},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(81)90026-3","volume":"3","author":"R. M. Karp","year":"1981","unstructured":"R. M. Karp and J. B. Orlin, \u201cParametric shortest path algorithms with an application to cyclic staffing,\u201d Disc. Appl. Math.\n3 (1981) 37\u201345.","journal-title":"Disc. Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"N. Katoh, T. Tokuyama, and K. Iwano, \u201cOn minimum and maximum spanning trees of linearly moving points\u201d, Proc. 33rd IEEE Symp. Found. Comput. Sci. (1992) 396\u2013405.","key":"15_CR17","DOI":"10.1109\/SFCS.1992.267750"},{"unstructured":"S. Khuller, B. Raghavachari, N. Young, \u201cBalancing minimum spanning and shortest path trees\u201d, Third Symposium on Discrete Algorithms, 1993.","key":"15_CR18"},{"doi-asserted-by":"crossref","unstructured":"V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, \u201cMulticasting for Multimedia Applications,\u201d Proc. of IEEE INFOCOM '92 (1992).","key":"15_CR19","DOI":"10.1109\/INFCOM.1992.263480"},{"key":"15_CR20","first-page":"66","volume":"No. 7","author":"V. P. Kozyrev","year":"1986","unstructured":"V. P. Kozyrev, \u201cFinding spanning trees that are optimal with respect to several ranked criteria,\u201d Combinatorial Analysis, No. 7 (1986) 66\u201373, 163\u2013164.","journal-title":"Combinatorial Analysis"},{"unstructured":"E. L. Lawler, \u201cOptimal cycles in doubly weighted directed linear graphs\u201d, Theory of Graphs, International Symposium, Gordon and Breach (1967) 209\u2013214.","key":"15_CR21"},{"unstructured":"H.-P. Lenhof, J. S. Salowe, and D. E. Wrege, \u201cTwo methods to mix shortest-path and minimum spanning trees,\u201d (1993), manuscript.","key":"15_CR22"},{"doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, \u201cApproximations and optimal geometric divide-and-conquer,\u201d Proc. Twenty-third ACM Symp. Theory Comput. (1991) 505\u2013511.","key":"15_CR23","DOI":"10.1145\/103418.103470"},{"issue":"4","key":"15_CR24","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N. Megiddo","year":"1979","unstructured":"N. Megiddo, \u201cCombinatorial optimization with rational objective functions,\u201d Math. Oper. Res.\n4(4) (1979) 414\u2013424.","journal-title":"Math. Oper. Res."},{"issue":"4","key":"15_CR25","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, \u201cApplying parallel computation algorithms in the design of serial algorithms,\u201d J. ACM\n30(4) (1983) 852\u2013865.","journal-title":"J. ACM"},{"unstructured":"R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, H. B. Hunt III, \u201cMany birds with one stone: Multi-objective approximation algorithms,\u201d Proc. 25th Symp. Theory Comput. (1993) 438\u2013447.","key":"15_CR26"},{"unstructured":"G. Robins, personal communication.","key":"15_CR27"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0030828","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:25:36Z","timestamp":1578525936000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0030828"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602163","9783540447337"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/bfb0030828","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"20 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}