{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:51:00Z","timestamp":1725663060165},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167617"},{"type":"electronic","value":"9783540398592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_89","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:52:02Z","timestamp":1330177922000},"page":"397-406","source":"Crossref","is-referenced-by-count":9,"title":["A very fast, practical algorithm for finding a negative cycle in a digraph"],"prefix":"10.1007","author":[{"given":"Paul","family":"Spirakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Athanasios","family":"Tsakalidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"41_CR1","unstructured":"AHO A., HOPCROFT J., ULLMAN J. \"Design and Analysis of Computer Algorithms\", Addison Wesley (1974)"},{"key":"41_CR2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"ANGLUIN D. and VALLANT L. \"Fast Probabilistic Algorithms for Hamiltonian Circuits and Mathings\" J. Computers and System Sciences, Vol.18, pp.155\u2013193 (1979)","journal-title":"J. Computers and System Sciences"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"CHERNOFF H. \"A Measure of Asymptotic Efficiency for Tests of a Hypothesis based on the Sum of Observations\", Annals of Math. Statistics, Vol.23 (1952)","DOI":"10.1214\/aoms\/1177729330"},{"key":"41_CR4","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erdos","year":"1959","unstructured":"ERDOS P. and RENYI A. \"On Random Graphs\", in the \"Art of Counting\", J.Spencer editor, MIT Press, also \"Publicationes Mathematicae\", Vol. 6, pp. 290\u2013297 (1959)","journal-title":"Publicationes Mathematicae"},{"key":"41_CR5","unstructured":"ERDOS P. and RENYI A. \"On the evolution on random graphs\", Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5, (1960)"},{"key":"41_CR6","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"HAREL D. and TARJAN R.E. \"Fast Algorithms for finding Nearest Common Ancestors\", SIAM Journal of Computing, Vol. 13, pp. 338\u2013355 (1984)","journal-title":"SIAM Journal of Computing"},{"key":"41_CR7","doi-asserted-by":"crossref","unstructured":"KARP R. and TARJAN R. \"Linear Expected-Time Algorithms for Connectivity Problems\", 12th ACM Symp. on Theory of Computing, pp. 368\u2013377 (1980)","DOI":"10.1016\/0196-6774(80)90017-6"},{"key":"41_CR8","unstructured":"LAWLER E.L. \"Combinatorial Optimization: Networks and Matroids\", Holt, Rinehart and Winston (1976)"},{"key":"41_CR9","unstructured":"LENGAUER T. \"Efficient Algorithms for The Constraint Generation for Intergrated Circuit Layout Compaction\", Proc. of 9-th Workshop on Graphtheoretic Concepts in Computer Science, Trauner Verlag, pp.219\u2013230 (1983)"},{"issue":"4","key":"41_CR10","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1137\/0208048","volume":"8","author":"D. Maier","year":"1979","unstructured":"MAIER D. \"An Efficient Method for Storing Ancestor Information in Trees\", SIAM Journal of Computing, Vol.8, No 4, pp.599\u2013618 (1979)","journal-title":"SIAM Journal of Computing"},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"MEHLHORN K. \"Data Structures and Algorithms, Vol.2: Graph-Algorithms and NP-Completeness\", EATCS Monographs on Theoretical Computer Science, Springer Verlag (1984)","DOI":"10.1007\/978-3-642-69897-2"},{"key":"41_CR12","unstructured":"PAPADIMITRIOU CH. and STEIGLITZ K. \"Combinatorial Optimization: Algorithms and Complexity\", Prentice-Hall (1982)"},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"REIF J. and SPIRAKIS P. \"Random Matroids\", 12th ACM Symp. on Theory of Computing, pp.385\u2013397 (1980)","DOI":"10.1145\/800141.804688"},{"key":"41_CR14","unstructured":"REIF J. and SPIRAKIS P. \"K-Connectivity of Random Undirected Graphs\" to appear in Journal of Discrete Mathematics"},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"SPIRAKIS P. and TSAKALIDIS A. \"A Very Fast, Practical Algorithm for Finding a Negative Cycle in a Digraph\", Technischer Bericht, FB 10, Universit\u00e4t des Saarlandes (1986)","DOI":"10.1007\/3-540-16761-7_89"},{"key":"41_CR16","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"TARJAN R.E. \"Data Structures and Network Algorithms\", Society for Industrial and Applied Mathematics, Philadelphia, PA (1983)"},{"key":"41_CR17","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF00289142","volume":"21","author":"A.K. Tsakalidis","year":"1984","unstructured":"TSAKALIDIS A.K. \"Maintaining Order in Generalized Linked List\", Acta Informatica, Vol. 21, pp. 101\u2013112 (1984)","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16761-7_89.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T13:44:14Z","timestamp":1687268654000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_89"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_89","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}