{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:49Z","timestamp":1725663289116},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540102915"},{"type":"electronic","value":"9783540384359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10291-4_25","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T12:10:27Z","timestamp":1330171827000},"page":"335-353","source":"Crossref","is-referenced-by-count":0,"title":["A birds eye view to path problems"],"prefix":"10.1007","author":[{"given":"Bernd","family":"Mahr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"25_CR1","unstructured":"A.V.Aho, J.E. Hopcroft, J.D.Ullman: Design and Analysis of Computer Algorithms, Addison-Wesley 1974"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"R.C. Backhouse, B.A. Carr\u00e9: Regular Algebra Applied to Path-finding Problems, J. Inst.Maths.Applics 15, 1975","DOI":"10.1093\/imamat\/15.2.161"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"P. Bloniarz: A Shortest Path Algorithm with Expected Time O (n2logn log*n), Proc. of the 12th ACM Symp. on Theory of Computing, Los Angeles, 1980","DOI":"10.1145\/800141.804687"},{"key":"25_CR4","unstructured":"P. Brucker: Theory of Matrix Algorithms, Math. Systems in Economics 13, Anton Hain, 1974"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"B.A. Carr\u00e9: An Algebra for Network Routing Problems, J. Inst. Maths. Applics 7, 1971","DOI":"10.1093\/imamat\/7.3.273"},{"key":"25_CR6","volume-title":"Graphs and Networks","author":"B. A. Carr\u00e9","year":"1979","unstructured":"\u2014: Graphs and Networks, Clarendon Press, Oxford, 1979"},{"key":"25_CR7","unstructured":"N. Christofides: Graph Theory, An Algorithmic Approach, Academic Press, 1975"},{"key":"25_CR8","unstructured":"J.H. Conway: Regular Algebra and Finite Machines, Chapman and Hall, 1971"},{"key":"25_CR9","unstructured":"W. Domschke: K\u00fcrzeste Wege in Graphen: Algorithmen, Verfahrensvergleiche, Mathematical Systems in Economics 2, Anton Hain, 1972"},{"key":"25_CR10","unstructured":"N. Deo, C. Pang: Shortest Path Algorithms: Taxonomy and Annotation, Washington State University, CS-80-057, 1980"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"S.E. Dreyfus: An Appraisal of Some Shortest Path Algorithms, Operations Research, 17, 1969","DOI":"10.1287\/opre.17.3.395"},{"key":"25_CR12","unstructured":"S. Eilenberg: Automata, Languages and Machines, Vol. A, Academic Press, 1974"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"M.J. Fischer, A.R. Meyer: Boolean Matrix Multiplication and Transitive Closure, IEEE 12th Ann. Symp. on Switching and Automata Theory, 1971","DOI":"10.1109\/SWAT.1971.4"},{"key":"25_CR14","unstructured":"L.R. Ford: Network Flow Theory, The Rand Corporation, P-923, 1956"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"M.L. Fredman: New Bounds on the Complexity of the Shortest Path Problem, SIAM J.Comp., Vol.5, 1976","DOI":"10.1137\/0205006"},{"key":"25_CR16","first-page":"5","volume":"11","author":"M. E. Furman","year":"1970","unstructured":"M.E. Furman: Application of a Method of Fast Multiplication of Matrices in the Problem of Finding the Transitive Closure of a Graph, Soviet Math. Dokl. 11:5, 1970","journal-title":"Soviet Math. Dokl."},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"B.L. Golden, T.L. Magnanti: Deterministic Network Optimization \u2014 a bibliography, Networks, 7, 1977","DOI":"10.1002\/net.3230070204"},{"key":"25_CR18","volume-title":"Graphes et Algorithmes","author":"M. Gondran","year":"1979","unstructured":"M. Gondran, M. Minoux: Graphes et Algorithmes, Eyrolles, Paris, 1979"},{"key":"25_CR19","unstructured":"M. Iri, M. Nakamori: Path Sets, Operator Semigroups and Shortest Path Algorithms on a Network, RAAG, Research Notes, Third Series, No. 185, Univ. Tokyo, 1972"},{"key":"25_CR20","unstructured":"D.B. Johnson: Algorithms for Shortest Paths, TR 73-169, Cornell University, 1973"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"\u2014: Efficient Algorithms for Shortest Paths in Networks, J. ACM 24, 1977","DOI":"10.1145\/321992.321993"},{"key":"25_CR22","unstructured":"L.R. Kerr: The Effect of Algebraic Structures on the Computational Complexity of Matrix Multiplication, Ph.D. Thesis, Cornell, 1970"},{"key":"25_CR23","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. Lawler","year":"1976","unstructured":"E. Lawler: Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"D.J. Lehmann: algebraic Structures for Transitive Closure, Theoretical Computer Science 4, 1977","DOI":"10.1016\/0304-3975(77)90056-1"},{"key":"25_CR25","unstructured":"C. Lautemann, B. Mahr: A Note on the Complexity of Path Problems, unpublished, 1980"},{"key":"25_CR26","unstructured":"B. Mahr: Algebraische Komplexit\u00e4t des allgemeinen Wegeproblems in Graphen, Techn. Univ. Berlin, Fachbereich Informatik, 79\u201314, 1979"},{"key":"25_CR27","unstructured":"\u2014: Semirings and Transitive Closure, in preparation, 1980"},{"key":"25_CR28","unstructured":"K. Mehlhorn: Effiziente Algorithmen, Teubner, 1977"},{"key":"25_CR29","unstructured":"J.D. Murchland: Shortest Distances by a Fixed Matrix Method, Report LBS-TNT-64, London, Graduate School of Business Studies, 1968 (see \/Br 74\/)"},{"key":"25_CR30","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0020-0190(71)90006-8","volume":"1","author":"J. Munro","year":"1971","unstructured":"J. Munro: Efficient Determination of the Transitive Closure of a Directed Graph, Information Processing Letters 1:2, 1971","journal-title":"Information Processing Letters"},{"key":"25_CR31","doi-asserted-by":"crossref","unstructured":"H. Noltemeier: Graphentheorie; mit Algorithmen und Anwendungen, de Gruyter, 1976","DOI":"10.1515\/9783110838442"},{"key":"25_CR32","unstructured":"M.S. Paterson: Complexity of Matrix Algorithms, handwritten copy, May 1974"},{"key":"25_CR33","unstructured":"U. Pape: Eine Bibliographie zu \"k\u00fcrzeste Wege in Graphen\", Techn. Univ. Berlin, FB 20, 1977"},{"key":"25_CR34","doi-asserted-by":"crossref","unstructured":"A.R. Pierce: Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree and Related Circuit Routing Problems, 1956\u20131974), Networks 5, 1975","DOI":"10.1002\/net.1975.5.2.129"},{"key":"25_CR35","doi-asserted-by":"crossref","unstructured":"V.R. Pratt: The Power of Negative Thinking in Multiplying Boolean Matrices, SIAM J.Comp. Vol. 4, 1975","DOI":"10.1137\/0204027"},{"key":"25_CR36","volume-title":"Theory of Automata","author":"A. Salomaa","year":"1969","unstructured":"A. Salomaa: Theory of Automata, Pergamon Press, Oxford, 1969"},{"key":"25_CR37","unstructured":"R.E. Tarjan: Solving Path Problems on Directed Graphs, Comp. Sci. Dept. Univ. Stanford, 1975"},{"key":"25_CR38","doi-asserted-by":"crossref","unstructured":"R.A. Wagner: A Shortest Path Algorithm for Edge Sparse Graphs, J. ACM, 23, 1976","DOI":"10.1145\/321921.321927"},{"key":"25_CR39","doi-asserted-by":"crossref","unstructured":"A. Wongseelashote: Semirings and Path Spaces, Discrete Math. 26, 1979","DOI":"10.1016\/0012-365X(79)90061-X"},{"key":"25_CR40","unstructured":"U. Zimmermann: Extract of a book submitted for publication, 1980"}],"container-title":["Lecture Notes in Computer Science","Graphtheoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10291-4_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T16:36:54Z","timestamp":1619541414000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10291-4_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540102915","9783540384359"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-10291-4_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}