All-Pairs Shortest Paths in O(n²) Time with High Probability

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n 2 ), in expectation and with high probability. This resolves a long standing open problem. The algorithm...

Full description

Saved in:
Bibliographic Details
Main Authors: Peres, Y, Sotnikov, D, Sudakov, B, Zwick, U
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Data structures
graph algorithms
Harmonic analysis
Heuristic algorithms
Probabilistic logic
random graphs
Random variables
shortest paths
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 672
container_issue
container_start_page 663
container_title
container_volume
creator Peres, Y
Sotnikov, D
Sudakov, B
Zwick, U
description We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n 2 ), in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n 2 ), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log 2 n) expected time.
doi_str_mv 10.1109/FOCS.2010.69
format conference_proceeding
fullrecord <record><control><sourceid>ieee_CHZPO</sourceid><recordid>TN_cdi_ieee_primary_5671327</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>5671327</ieee_id><sourcerecordid>5671327</sourcerecordid><originalsourceid>FETCH-LOGICAL-i175t-a2bf85d2e21fa17b0027fd212d3601c8af58fd074d2e2f79d3f571b1844e850f3</originalsourceid><addsrcrecordid>eNpNjsFKAzEURQNasK3u3LnJUhdT33tJJunCRRlaKxRmoHVdMk7iRKatTALS3_IT_DIrunB174HL4TJ2jTBBhOn9oizWE4IT5tMzNkJJUhpFypyzIZCmTEkyg3_9go1ifAOQoEAM2cOs67LKhj7ydXvok4uJVza1kYc9L2_3X593fBN2jn-E1PJleG151R9qW4cupOMlG3jbRXf1l2P2vJhvimW2Kh-fitkqC6hVyizV3qiGHKG3qGs4vfENITUiB3wx1ivjG9DyZ-L1tBFeaazRSOmMAi_G7ObXG5xz2_c-7Gx_3KpcoyAtvgGkrUfO</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>All-Pairs Shortest Paths in O(n²) Time with High Probability</title><source>IEEE Xplore All Conference Series</source><creator>Peres, Y ; Sotnikov, D ; Sudakov, B ; Zwick, U</creator><creatorcontrib>Peres, Y ; Sotnikov, D ; Sudakov, B ; Zwick, U</creatorcontrib><description>We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n 2 ), in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n 2 ), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log 2 n) expected time.</description><identifier>ISSN: 0272-5428</identifier><identifier>ISBN: 1424485258</identifier><identifier>ISBN: 9781424485253</identifier><identifier>DOI: 10.1109/FOCS.2010.69</identifier><identifier>LCCN: 0272-5428</identifier><language>eng</language><publisher>IEEE</publisher><subject>Algorithm design and analysis ; Data structures ; graph algorithms ; Harmonic analysis ; Heuristic algorithms ; Probabilistic logic ; random graphs ; Random variables ; shortest paths ; Upper bound</subject><ispartof>2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, p.663-672</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/5671327$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,27925,54555,54920,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/5671327$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Peres, Y</creatorcontrib><creatorcontrib>Sotnikov, D</creatorcontrib><creatorcontrib>Sudakov, B</creatorcontrib><creatorcontrib>Zwick, U</creatorcontrib><title>All-Pairs Shortest Paths in O(n²) Time with High Probability</title><title>2010 IEEE 51st Annual Symposium on Foundations of Computer Science</title><addtitle>focs</addtitle><description>We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n 2 ), in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n 2 ), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log 2 n) expected time.</description><subject>Algorithm design and analysis</subject><subject>Data structures</subject><subject>graph algorithms</subject><subject>Harmonic analysis</subject><subject>Heuristic algorithms</subject><subject>Probabilistic logic</subject><subject>random graphs</subject><subject>Random variables</subject><subject>shortest paths</subject><subject>Upper bound</subject><issn>0272-5428</issn><isbn>1424485258</isbn><isbn>9781424485253</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2010</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNpNjsFKAzEURQNasK3u3LnJUhdT33tJJunCRRlaKxRmoHVdMk7iRKatTALS3_IT_DIrunB174HL4TJ2jTBBhOn9oizWE4IT5tMzNkJJUhpFypyzIZCmTEkyg3_9go1ifAOQoEAM2cOs67LKhj7ydXvok4uJVza1kYc9L2_3X593fBN2jn-E1PJleG151R9qW4cupOMlG3jbRXf1l2P2vJhvimW2Kh-fitkqC6hVyizV3qiGHKG3qGs4vfENITUiB3wx1ivjG9DyZ-L1tBFeaazRSOmMAi_G7ObXG5xz2_c-7Gx_3KpcoyAtvgGkrUfO</recordid><startdate>201010</startdate><enddate>201010</enddate><creator>Peres, Y</creator><creator>Sotnikov, D</creator><creator>Sudakov, B</creator><creator>Zwick, U</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>201010</creationdate><title>All-Pairs Shortest Paths in O(n²) Time with High Probability</title><author>Peres, Y ; Sotnikov, D ; Sudakov, B ; Zwick, U</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i175t-a2bf85d2e21fa17b0027fd212d3601c8af58fd074d2e2f79d3f571b1844e850f3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2010</creationdate><topic>Algorithm design and analysis</topic><topic>Data structures</topic><topic>graph algorithms</topic><topic>Harmonic analysis</topic><topic>Heuristic algorithms</topic><topic>Probabilistic logic</topic><topic>random graphs</topic><topic>Random variables</topic><topic>shortest paths</topic><topic>Upper bound</topic><toplevel>online_resources</toplevel><creatorcontrib>Peres, Y</creatorcontrib><creatorcontrib>Sotnikov, D</creatorcontrib><creatorcontrib>Sudakov, B</creatorcontrib><creatorcontrib>Zwick, U</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library (IEL)</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Peres, Y</au><au>Sotnikov, D</au><au>Sudakov, B</au><au>Zwick, U</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>All-Pairs Shortest Paths in O(n²) Time with High Probability</atitle><btitle>2010 IEEE 51st Annual Symposium on Foundations of Computer Science</btitle><stitle>focs</stitle><date>2010-10</date><risdate>2010</risdate><spage>663</spage><epage>672</epage><pages>663-672</pages><issn>0272-5428</issn><isbn>1424485258</isbn><isbn>9781424485253</isbn><abstract>We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n 2 ), in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n 2 ), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log 2 n) expected time.</abstract><pub>IEEE</pub><doi>10.1109/FOCS.2010.69</doi><tpages>10</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 0272-5428
ispartof 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, p.663-672
issn 0272-5428
language eng
recordid cdi_ieee_primary_5671327
source IEEE Xplore All Conference Series
subjects Algorithm design and analysis
Data structures
graph algorithms
Harmonic analysis
Heuristic algorithms
Probabilistic logic
random graphs
Random variables
shortest paths
Upper bound
title All-Pairs Shortest Paths in O(n²) Time with High Probability
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-28T08%3A31%3A41IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=All-Pairs%20Shortest%20Paths%20in%20O(n%C2%B2)%20Time%20with%20High%20Probability&rft.btitle=2010%20IEEE%2051st%20Annual%20Symposium%20on%20Foundations%20of%20Computer%20Science&rft.au=Peres,%20Y&rft.date=2010-10&rft.spage=663&rft.epage=672&rft.pages=663-672&rft.issn=0272-5428&rft.isbn=1424485258&rft.isbn_list=9781424485253&rft_id=info:doi/10.1109/FOCS.2010.69&rft_dat=%3Cieee_CHZPO%3E5671327%3C/ieee_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i175t-a2bf85d2e21fa17b0027fd212d3601c8af58fd074d2e2f79d3f571b1844e850f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=5671327&rfr_iscdi=true