{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T17:48:31Z","timestamp":1673459311206},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2000,1]]},"abstract":"\n Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. This gap, known in the literature as the \u201ctransitive closure bottleneck,\u201d poses a long-standing open problem. Our main result is an O(mn\n \n \u03f5\n 0<\/jats:sub>\n <\/jats:sup>\n +s( m+n\n \n 1+\u03f5\n 0<\/jats:sub>\n <\/jats:sup>\n )) work polylog-time randomized algorithm that computes paths within (1 +\n O<\/jats:italic>\n (1\/polylog\n n<\/jats:italic>\n ) of shortest from\n s<\/jats:italic>\n source nodes to all other nodesin weighted undirected networks with\n n<\/jats:italic>\n nodes and\n m<\/jats:italic>\n edges (for any fixed \u03f5\n 0<\/jats:sub>\n >0). This work bound nearly matches the \u00d5(sm) sequential time. In contrast, previous polylog-time algorithms required min {\u00d5(n\n 3<\/jats:sup>\n ), \u00d5(m\n 2<\/jats:sup>\n )} work (even when\n s<\/jats:italic>\n =1), and previous near-linear work algorithms required near-\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) time. We also present faster sequential algorithms that provide good approximate distances only between \u201cdistant\u201d vertices: We obtain an\n \n O((m + sn)n\n \u03f50<\/jats:sup>\n <\/jats:italic>\n time algorithm that computes paths of weight (1+\n O<\/jats:italic>\n (1\/polylog\n n<\/jats:italic>\n ) dist +\n O<\/jats:italic>\n (\n w<\/jats:italic>\n max<\/jats:sub>\n polylog\n n<\/jats:italic>\n ), where dist is the corresponding distance and\n w<\/jats:italic>\n max<\/jats:sub>\n is the maximum edge weight. Our chief instrument, which is of independent interest, are efficient constructions of sparse\n hop sets<\/jats:italic>\n . A (\n d<\/jats:italic>\n ,\u03f5)-hop set of a network\n G<\/jats:italic>\n =(\n V,E<\/jats:italic>\n ) is a set\n E<\/jats:italic>\n * of new weighted edges such that mimimum-weight\n d<\/jats:italic>\n -edge paths in (\n V, E,<\/jats:italic>\n \u222a\n E*<\/jats:italic>\n ) have weight within (1+\u03f5) of the respective distances in\n G<\/jats:italic>\n . We construct hop sets of size\n O<\/jats:italic>\n (n\n 1+\u03f50<\/jats:sup>\n ) where \u03f5=\n O<\/jats:italic>\n (1\/polylog\n n<\/jats:italic>\n ) and\n d<\/jats:italic>\n =\n O<\/jats:italic>\n (polylog\n n<\/jats:italic>\n ).\n <\/jats:p>","DOI":"10.1145\/331605.331610","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"132-166","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["Polylog-time and near-linear work approximation scheme for undirected shortest paths"],"prefix":"10.1145","volume":"47","author":[{"given":"Edith","family":"Cohen","sequence":"first","affiliation":[{"name":"AT&T Labs, Florham Park, NJ"}]}],"member":"320","published-online":{"date-parts":[[2000,1]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"638","volume-title":"Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"AWERBUCH B.","year":"1993","unstructured":"AWERBUCH , B. , BERGER , B. , COWEN , L. , AND PELEG , D. 1993 . Near-linear cost sequential and distributed constructions of sparse neighborhood covers . In Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 638 - 647 . AWERBUCH, B., BERGER, B., COWEN, L., AND PELEG, D. 1993. Near-linear cost sequential and distributed constructions of sparse neighborhood covers. In Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 638-647."},{"key":"e_1_2_1_2_1","first-page":"503","volume-title":"Proceedings of the 31st IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"AWERBUCH B.","year":"1990","unstructured":"AWERBUCH , B. , AND PELEG , D. 1990 . Sparse partitions . In Proceedings of the 31st IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 503 - 513 . AWERBUCH, B., AND PELEG, D. 1990. Sparse partitions. In Proceedings of the 31st IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 503-513."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0048"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0813"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"e_1_2_1_6_1","volume-title":"Introduction to Algorithms","author":"CORMEN T.","unstructured":"CORMEN , T. , LEISERSON , C. , AND RIVEST , R. 1990. Introduction to Algorithms . McGraw-Hill , New York . CORMEN, T., LEISERSON, C., AND RIVEST, R. 1990. Introduction to Algorithms. McGraw-Hill, New York."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"KLEIN P. N. 1992. A parallel randomized approximation scheme for shortest paths. Draft of journal version. KLEIN P. N. 1992. A parallel randomized approximation scheme for shortest paths. Draft of journal version.","DOI":"10.1145\/129712.129785"},{"key":"e_1_2_1_8_1","first-page":"750","volume-title":"Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM","author":"KLEIN P. N.","year":"1992","unstructured":"KLEIN , P. N. , AND SAIRAM , S. 1992 . A parallel randomized approximation scheme for shortest paths . In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM , New York , pp. 750 - 758 . 10.1145\/129712.129785 KLEIN, P. N., AND SAIRAM, S. 1992. A parallel randomized approximation scheme for shortest paths. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 750-758. 10.1145\/129712.129785"},{"key":"e_1_2_1_9_1","first-page":"259","volume-title":"Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"KLEIN P. N.","year":"1993","unstructured":"KLEIN , P. N. , AND SAIRAM , S. 1993 . A linear-processor polylog-time algorithm for shortest paths in planar graphs . In Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 259 - 270 . KLEIN, P. N., AND SAIRAM, S. 1993. A linear-processor polylog-time algorithm for shortest paths in planar graphs. In Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 259-270."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265923"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220006"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/331605.331610","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T06:28:34Z","timestamp":1672554514000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/331605.331610"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1145\/331605.331610"],"URL":"http:\/\/dx.doi.org\/10.1145\/331605.331610","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2000,1]]},"assertion":[{"value":"2000-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}