{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2020,2,16]],"date-time":"2020-02-16T18:40:05Z","timestamp":1581878405341},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1995,3]]},"DOI":"10.1145\/201019.201022","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"321-328","source":"Crossref","is-referenced-by-count":208,"title":["A randomized linear-time algorithm to find minimum spanning trees"],"prefix":"10.1145","volume":"42","author":[{"given":"David R.","family":"Karger","sequence":"first","affiliation":[{"name":"Stanford Univ., Stanford, CA"}]},{"given":"Philip N.","family":"Klein","sequence":"additional","affiliation":[{"name":"Brown Univ., Providence, RI"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton Univ., Princeton, NJ; and NEC Research Institute, Princeton, NJ"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","unstructured":"Wiley New York Wiley N. ~ALON J. H. SPENCER The Probabilistic Method 1992 223"},{"key":"e_1_2_1_2_1","unstructured":"~BOR0VKA O. 1926. O jistdm probl~mu minimfdnfm. Pr~ca Moravskd P~irodoL ~deckd Spole6nosti ~3 37 58. (In Czech.) ~BOR0VKA O. 1926. O jistdm probl~mu minimfdnfm. Pr~ca Moravskd P~irodoL ~deckd Spole6nosti ~3 37 58. (In Czech.)"},{"key":"e_1_2_1_3_1","unstructured":"Proceedings of the 17th hzternational Colloquium on Automata Languages and ~Programming. Lecture Notes in Computer Science Springer-Verlag New York Proceedings of the 17th hzternational Colloquium on Automata Languages and ~Programming. Lecture Notes in Computer Science 443 J. ~CHERIYAN T. HAGERUP K. MEHLHORN Can a maximum flow be computed in ~O(nm) time? 1990 235 248 10.5555\/90397.90431"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of the asymptotic efficiency for tests of a hypothesis based on ~the sum of observations","volume":"23","author":"~HERNOFF H.","year":"1952","journal-title":"Anm Math. Stat."},{"key":"e_1_2_1_5_1","unstructured":"Proceedings of the 6th Symposium on Parallel Algorithms and ~Architectures. (Cape May N.J. June 27-29) New York Proceedings of the 6th Symposium on Parallel Algorithms and ~Architectures. (Cape May N.J. June 27-29) R. ~COLE P. N. KLEIN R. E. TARJAN A linear-work parallel algorithm for finding ~minimum spanning trees 1994 11 15"},{"key":"e_1_2_1_6_1","unstructured":"Proceedings of the 27th Annual IEEE Symposium on Founda- ~ttons of Computer Science. IEEE Computer Society Press Los Alamitos Calif. Proceedings of the 27th Annual IEEE Symposium on Founda- ~ttons of Computer Science. IEEE Computer Society Press Los Alamitos Calif. R. ~COLE U. VISHKIN Approximate and exact parallel scheduling with applications to ~list tree and graph problems 1986 478 491"},{"key":"e_1_2_1_7_1","DOI":"10.1137\/0221070","doi-asserted-by":"publisher"},{"key":"e_1_2_1_8_1","unstructured":"~FELLER W. 1968. An Introduction to Probability Theory and Its Applications. Vol. 1. Wiley New ~York. ~FELLER W. 1968. An Introduction to Probability Theory and Its Applications. Vol. 1. Wiley New ~York."},{"key":"e_1_2_1_9_1","unstructured":"Proceedings of the 31st Annual IEEE Symposium on Foundations of ~Computer Sctence. IEEE Computer Society Press Los Alamitos Calif. Proceedings of the 31st Annual IEEE Symposium on Foundations of ~Computer Sctence. IEEE Computer Society Press Los Alamitos Calif. M ~FREDMAN D. E. WILLARD Trans-dichotomous algonthms for minimum spanning ~trees and shortest paths 1990 719"},{"key":"e_1_2_1_10_1","unstructured":"Proceedings of the 25th Annual IEEE Symposium on Founda- ~tions of Computer Science. 1EEE Computer Society Press Los Alamltos Calif. Proceedings of the 25th Annual IEEE Symposium on Founda- ~tions of Computer Science. 1EEE Computer Society Press Los Alamltos Calif. H. N. ~GABOW Z. GALIL T. H. SPENCER Efficient implementation of graph ~algorithms using contraction 1984 347 357"},{"key":"e_1_2_1_11_1","DOI":"10.1007\/BF02579168","doi-asserted-by":"publisher"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","article-title":"On the history of the minimum spanning tree problem. ~Ann","volume":"7","author":"~GRAHAM R. L.","year":"1985","journal-title":"Hist. Comput."},{"key":"e_1_2_1_13_1","unstructured":"~KARGER D. R. 1992. Approximating verifying and constructing minimum spanning forests. ~Manuscript. ~KARGER D. R. 1992. Approximating verifying and constructing minimum spanning forests. ~Manuscript."},{"key":"e_1_2_1_14_1","unstructured":"Proceedings of the 4th Annual ACM-SIAM Sympostum on Discrete Algortthms. ~ACM New York Proceedings of the 4th Annual ACM-SIAM Sympostum on Discrete Algortthms. ~ACM D. R. ~KARGER Global rain-cuts in RNC and other ramifications of a simple mincut ~algorithm 1993 21 30 10.5555\/313559.313605"},{"key":"e_1_2_1_15_1","unstructured":"Proceedings of the 34th Annual IEEE Symposium on Founda- ~tions of Computer Science. IEEE Computer Society Press Los Alamitos Calif. Proceedings of the 34th Annual IEEE Symposium on Founda- ~tions of Computer Science. IEEE Computer Society Press Los Alamitos Calif. D. R. ~KARGER Random sampling in matroids with applications to graph connectivity ~and minimum spanning trees 1993 84 93"},{"key":"e_1_2_1_16_1","unstructured":"Mass. Mass. R. M. ~KARP V. RAMACHANDRAN A survey of parallel algorithms for shared-memory ~machines. In Handbook of Theoretical Computer Science Volume A: Algorithms and Complexity ~J. van Leeuwen ed. MIT Press Cambridge 1990 869 10.5555\/114872.114889","DOI":"10.1016\/B978-0-444-88071-0.50022-9","doi-asserted-by":"crossref"},{"key":"e_1_2_1_17_1","unstructured":"Proceedings of the ~Workshop on Algorithms and Data Structures Proceedings of the ~Workshop on Algorithms and Data Structures V. ~KING A simpler minimum spanning tree verification algorithm 1995 10.5555\/645930.672859","DOI":"10.1007\/3-540-60220-8_83","doi-asserted-by":"crossref"},{"key":"e_1_2_1_18_1","unstructured":"Proceedings' of the 26th Annual ACM Symposium on Theory of Computing. ~(Montreal Que. Canada May 23-25) New York Proceedings' of the 26th Annual ACM Symposium on Theory of Computing. ~(Montreal Que. Canada May 23-25) P. N. ~KLEIN R. E. TARJAN A randomized linear-time algorithm for finding minimum ~spanning trees 1994 9 15 10.1145\/195058.195084 10.1145\/195058.195084 10.1145\/195058.195084"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF02579443","article-title":"Linear verification for spanning trees","volume":"5","author":"KOML S, J","year":"1985","journal-title":"Combinatorica"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the shortest spanning subtree of a graph and the traveling salesman ~problem","volume":"7","author":"~KRUSKAL J. B.","year":"1956","journal-title":"Proc. Amer. Math. Soc."},{"key":"e_1_2_1_21_1","unstructured":"~RAGHAVAN P. 1990. Lecture notes on randomized algorithms. Res. Rep. RC 15340 (#68237). ~Computer Science\/Mathematics. IBM Research Division T. J. Watson Research Center ~Yorktown Heights N.Y. p. 54. ~RAGHAVAN P. 1990. Lecture notes on randomized algorithms. Res. Rep. RC 15340 (#68237). ~Computer Science\/Mathematics. IBM Research Division T. J. Watson Research Center ~Yorktown Heights N.Y. p. 54."},{"key":"e_1_2_1_22_1","DOI":"10.1145\/322154.322161","doi-asserted-by":"publisher"},{"key":"e_1_2_1_23_1","unstructured":"~TARJAN R. E. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied ~Mathematics Philadelphia Pa. Chap. 6. ~TARJAN R. E. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied ~Mathematics Philadelphia Pa. Chap. 6."}],"container-title":["Journal of the ACM (JACM)"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=201022&ftid=27399&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,16]],"date-time":"2020-02-16T18:17:37Z","timestamp":1581877057000},"score":1.0,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":23,"journal-issue":{"published-print":{"date-parts":[[1995,3]]},"issue":"2"},"alternative-id":["10.1145\/201019.201022"],"URL":"http:\/\/dx.doi.org\/10.1145\/201019.201022","relation":{"cites":[]},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Control and Systems Engineering","Hardware and Architecture","Software","Artificial Intelligence","Information Systems"]}}