{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T07:52:14Z","timestamp":1718092334891},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1998,6,1]],"date-time":"1998-06-01T00:00:00Z","timestamp":896659200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[1998,6]]},"DOI":"10.1007\/bf02684360","type":"journal-article","created":{"date-parts":[[2007,8,22]],"date-time":"2007-08-22T07:52:51Z","timestamp":1187769171000},"page":"109-119","source":"Crossref","is-referenced-by-count":1,"title":["Spanning trees and shortest paths in monge graphs"],"prefix":"10.1007","volume":"60","author":[{"given":"T.","family":"Dud\u00e1s","sequence":"first","affiliation":[]},{"given":"R.","family":"Rudolf","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02684360_CR1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M. M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica2, 195\u2013208 (1987).","journal-title":"Algorithmica"},{"key":"BF02684360_CR2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF02019153","volume":"6","author":"R. E. Burkard","year":"1990","unstructured":"Burkard, R. E.: Special cases of the travelling salesman problem and heuristics. Acta Math. Appl. Sin.6, 273\u2013288 (1990).","journal-title":"Acta Math. Appl. Sin."},{"key":"BF02684360_CR3","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"R. E. Burkard","year":"1996","unstructured":"Burkard, R. E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discr. Appl. Math.70, 95\u2013161 (1996).","journal-title":"Discr. Appl. Math."},{"key":"BF02684360_CR4","unstructured":"Burkard, R. E., De\u012dneko, V., van Dal, R., van der Veen, J. A. A., Woeginger, G. J.: Well-solvable cases of the TSP: A survey. SFB-Report No. 52, SFB \u2018Optimierung und Kontrolle\u2019, Institute of Mathematics, University of Technology, Graz, Austria, December 1995, submitted for publication."},{"key":"BF02684360_CR5","doi-asserted-by":"crossref","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 connection with graphs. Numer. Math.1, 269\u2013271 (1959).","journal-title":"Numer. Math."},{"key":"BF02684360_CR6","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R. W. Floyd","year":"1962","unstructured":"Floyd, R. W.: Algorithm 97 (Shortest Path). Comm. ACM5, 345 (1962).","journal-title":"Comm. ACM"},{"key":"BF02684360_CR7","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"Fredman, M. L., Tarjan, R. E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Comput. Mach.34, 596\u2013615 (1987).","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02684360_CR8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H. N. Gabow","year":"1986","unstructured":"Gabow, H. N., Galil, Z., Spencer, T., Tarjan, R. E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica6, 109\u2013122 (1986).","journal-title":"Combinatorica"},{"key":"BF02684360_CR9","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/BF01294129","volume":"44","author":"S. Khuller","year":"1995","unstructured":"Khuller, S., Raghavachari, B., Young, N.: Balancing minimum spanning trees and shortest-path trees. Algorithmica44, 305\u2013321 (1995).","journal-title":"Algorithmica"},{"key":"BF02684360_CR10","doi-asserted-by":"crossref","unstructured":"Klein, P., Tarjan, R. E.: A randomized linear-time algorithm for finding minimum spanning trees. Proc. 26th Annual Symposium on Theory of Computing, pp. 9\u201315 (1994).","DOI":"10.1145\/195058.195084"},{"key":"BF02684360_CR11","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0167-6377(94)90037-X","volume":"16","author":"U. Pferschy","year":"1994","unstructured":"Pferschy, U., Rudolf, R., Woeginger, G. J.: Monge matrices make maximization manageable. Oper. Res. Lett.16, 245\u2013254 (1994).","journal-title":"Oper. Res. Lett."},{"key":"BF02684360_CR12","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. Bell System Tech. J.36, 1389\u20131401 (1957).","journal-title":"Bell System Tech. J."},{"key":"BF02684360_CR13","doi-asserted-by":"crossref","first-page":"179","DOI":"10.2307\/1970124","volume":"66","author":"F. Supnick","year":"1957","unstructured":"Supnick, F.: Extreme Hamiltonian lines. Ann. Math.66, 179\u2013201 (1957).","journal-title":"Ann. Math."},{"key":"BF02684360_CR14","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/0196-6774(88)90032-6","volume":"9","author":"R. Wilber","year":"1988","unstructured":"Wilber, R.: The concave least-weight subsequence problem revisited. J. Algorithms9, 418\u2013425 (1988).","journal-title":"J. Algorithms"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02684360.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02684360\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02684360","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T21:31:14Z","timestamp":1684013474000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02684360"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,6]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,6]]}},"alternative-id":["BF02684360"],"URL":"https:\/\/doi.org\/10.1007\/bf02684360","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,6]]}}}