Loading…
A fully dynamic algorithm for distributed shortest paths
We propose a fully dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If Δ σ is the number of pairs of nodes changing the distance after a single edge modification σ ( insert, delete, weight decrease, or weight increase) then t...
Saved in:
| Published in: | Theoretical computer science 2003-03, Vol.297 (1), p.83-102 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c368t-84256926236f97f2eed21014067767c23b8826984b37ae5352a61d8a9d6965a13 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c368t-84256926236f97f2eed21014067767c23b8826984b37ae5352a61d8a9d6965a13 |
| container_end_page | 102 |
| container_issue | 1 |
| container_start_page | 83 |
| container_title | Theoretical computer science |
| container_volume | 297 |
| creator | Cicerone, Serafino Di Stefano, Gabriele Frigioni, Daniele Nanni, Umberto |
| description | We propose a fully dynamic distributed algorithm for the
all-pairs shortest paths problem on general networks with positive real edge weights. If
Δ
σ
is the number of pairs of nodes changing the distance after a single edge modification
σ (
insert,
delete,
weight decrease, or
weight increase) then the message complexity of the proposed algorithm is O(
nΔ
σ
) in the worst case, where
n is the number of nodes of the network. If
Δ
σ
=
o(n
2)
, this is better than recomputing everything from scratch after each edge modification. Up to now only a result of Ramarao and Venkatesan was known, stating that the problem of updating shortest paths in a dynamic distributed environment is as hard as that of computing shortest paths. |
| doi_str_mv | 10.1016/S0304-3975(02)00619-9 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_27870964</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0304397502006199</els_id><sourcerecordid>27870964</sourcerecordid><originalsourceid>FETCH-LOGICAL-c368t-84256926236f97f2eed21014067767c23b8826984b37ae5352a61d8a9d6965a13</originalsourceid><addsrcrecordid>eNqFkElLBDEQhYMoOI7-BKEvih5as3RXkpMMgxsMeFDPIZOknUgvY5IW-t_bs6BH61KX79V79RA6J_iGYAK3r5jhImeSl1eYXmMMRObyAE2I4DKnVBaHaPKLHKOTGD_xOCWHCRKzrOrresjs0OrGm0zXH13wadVkVRcy62MKftknZ7O46kJyMWVrnVbxFB1Vuo7ubL-n6P3h_m3-lC9eHp_ns0VuGIiUi4KWIClQBpXkFXXO0jF0gYFz4IaypRAUpCiWjGtXspJqIFZoaUFCqQmbosvd3XXovvrRXjU-GlfXunVdHxXlgmMJxQiWO9CELsbgKrUOvtFhUASrTU9q25PalKAwVduelBx1F3sDHY2uq6Bb4-OfuOCAQWyC3O04N3777V1Q0XjXGmd9cCYp2_l_nH4AAS56gQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>27870964</pqid></control><display><type>article</type><title>A fully dynamic algorithm for distributed shortest paths</title><source>ScienceDirect Freedom Collection 2022-2024</source><creator>Cicerone, Serafino ; Di Stefano, Gabriele ; Frigioni, Daniele ; Nanni, Umberto</creator><creatorcontrib>Cicerone, Serafino ; Di Stefano, Gabriele ; Frigioni, Daniele ; Nanni, Umberto</creatorcontrib><description>We propose a fully dynamic distributed algorithm for the
all-pairs shortest paths problem on general networks with positive real edge weights. If
Δ
σ
is the number of pairs of nodes changing the distance after a single edge modification
σ (
insert,
delete,
weight decrease, or
weight increase) then the message complexity of the proposed algorithm is O(
nΔ
σ
) in the worst case, where
n is the number of nodes of the network. If
Δ
σ
=
o(n
2)
, this is better than recomputing everything from scratch after each edge modification. Up to now only a result of Ramarao and Venkatesan was known, stating that the problem of updating shortest paths in a dynamic distributed environment is as hard as that of computing shortest paths.</description><identifier>ISSN: 0304-3975</identifier><identifier>EISSN: 1879-2294</identifier><identifier>DOI: 10.1016/S0304-3975(02)00619-9</identifier><identifier>CODEN: TCSCDI</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Algebra ; Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Combinatorics ; Combinatorics. Ordered structures ; Computer science; control theory; systems ; Exact sciences and technology ; General algebraic systems ; Graph theory ; Mathematical programming ; Mathematics ; Operational research and scientific management ; Operational research. Management science ; Sciences and techniques of general use ; Theoretical computing</subject><ispartof>Theoretical computer science, 2003-03, Vol.297 (1), p.83-102</ispartof><rights>2002 Elsevier Science B.V.</rights><rights>2003 INIST-CNRS</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c368t-84256926236f97f2eed21014067767c23b8826984b37ae5352a61d8a9d6965a13</citedby><cites>FETCH-LOGICAL-c368t-84256926236f97f2eed21014067767c23b8826984b37ae5352a61d8a9d6965a13</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>309,310,314,780,784,789,790,23930,23931,25140,27924,27925</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=14760681$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Cicerone, Serafino</creatorcontrib><creatorcontrib>Di Stefano, Gabriele</creatorcontrib><creatorcontrib>Frigioni, Daniele</creatorcontrib><creatorcontrib>Nanni, Umberto</creatorcontrib><title>A fully dynamic algorithm for distributed shortest paths</title><title>Theoretical computer science</title><description>We propose a fully dynamic distributed algorithm for the
all-pairs shortest paths problem on general networks with positive real edge weights. If
Δ
σ
is the number of pairs of nodes changing the distance after a single edge modification
σ (
insert,
delete,
weight decrease, or
weight increase) then the message complexity of the proposed algorithm is O(
nΔ
σ
) in the worst case, where
n is the number of nodes of the network. If
Δ
σ
=
o(n
2)
, this is better than recomputing everything from scratch after each edge modification. Up to now only a result of Ramarao and Venkatesan was known, stating that the problem of updating shortest paths in a dynamic distributed environment is as hard as that of computing shortest paths.</description><subject>Algebra</subject><subject>Algorithmics. Computability. Computer arithmetics</subject><subject>Applied sciences</subject><subject>Combinatorics</subject><subject>Combinatorics. Ordered structures</subject><subject>Computer science; control theory; systems</subject><subject>Exact sciences and technology</subject><subject>General algebraic systems</subject><subject>Graph theory</subject><subject>Mathematical programming</subject><subject>Mathematics</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><subject>Sciences and techniques of general use</subject><subject>Theoretical computing</subject><issn>0304-3975</issn><issn>1879-2294</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2003</creationdate><recordtype>article</recordtype><recordid>eNqFkElLBDEQhYMoOI7-BKEvih5as3RXkpMMgxsMeFDPIZOknUgvY5IW-t_bs6BH61KX79V79RA6J_iGYAK3r5jhImeSl1eYXmMMRObyAE2I4DKnVBaHaPKLHKOTGD_xOCWHCRKzrOrresjs0OrGm0zXH13wadVkVRcy62MKftknZ7O46kJyMWVrnVbxFB1Vuo7ubL-n6P3h_m3-lC9eHp_ns0VuGIiUi4KWIClQBpXkFXXO0jF0gYFz4IaypRAUpCiWjGtXspJqIFZoaUFCqQmbosvd3XXovvrRXjU-GlfXunVdHxXlgmMJxQiWO9CELsbgKrUOvtFhUASrTU9q25PalKAwVduelBx1F3sDHY2uq6Bb4-OfuOCAQWyC3O04N3777V1Q0XjXGmd9cCYp2_l_nH4AAS56gQ</recordid><startdate>20030317</startdate><enddate>20030317</enddate><creator>Cicerone, Serafino</creator><creator>Di Stefano, Gabriele</creator><creator>Frigioni, Daniele</creator><creator>Nanni, Umberto</creator><general>Elsevier B.V</general><general>Elsevier</general><scope>6I.</scope><scope>AAFTH</scope><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20030317</creationdate><title>A fully dynamic algorithm for distributed shortest paths</title><author>Cicerone, Serafino ; Di Stefano, Gabriele ; Frigioni, Daniele ; Nanni, Umberto</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c368t-84256926236f97f2eed21014067767c23b8826984b37ae5352a61d8a9d6965a13</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2003</creationdate><topic>Algebra</topic><topic>Algorithmics. Computability. Computer arithmetics</topic><topic>Applied sciences</topic><topic>Combinatorics</topic><topic>Combinatorics. Ordered structures</topic><topic>Computer science; control theory; systems</topic><topic>Exact sciences and technology</topic><topic>General algebraic systems</topic><topic>Graph theory</topic><topic>Mathematical programming</topic><topic>Mathematics</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><topic>Sciences and techniques of general use</topic><topic>Theoretical computing</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Cicerone, Serafino</creatorcontrib><creatorcontrib>Di Stefano, Gabriele</creatorcontrib><creatorcontrib>Frigioni, Daniele</creatorcontrib><creatorcontrib>Nanni, Umberto</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Cicerone, Serafino</au><au>Di Stefano, Gabriele</au><au>Frigioni, Daniele</au><au>Nanni, Umberto</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A fully dynamic algorithm for distributed shortest paths</atitle><jtitle>Theoretical computer science</jtitle><date>2003-03-17</date><risdate>2003</risdate><volume>297</volume><issue>1</issue><spage>83</spage><epage>102</epage><pages>83-102</pages><issn>0304-3975</issn><eissn>1879-2294</eissn><coden>TCSCDI</coden><abstract>We propose a fully dynamic distributed algorithm for the
all-pairs shortest paths problem on general networks with positive real edge weights. If
Δ
σ
is the number of pairs of nodes changing the distance after a single edge modification
σ (
insert,
delete,
weight decrease, or
weight increase) then the message complexity of the proposed algorithm is O(
nΔ
σ
) in the worst case, where
n is the number of nodes of the network. If
Δ
σ
=
o(n
2)
, this is better than recomputing everything from scratch after each edge modification. Up to now only a result of Ramarao and Venkatesan was known, stating that the problem of updating shortest paths in a dynamic distributed environment is as hard as that of computing shortest paths.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/S0304-3975(02)00619-9</doi><tpages>20</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0304-3975 |
| ispartof | Theoretical computer science, 2003-03, Vol.297 (1), p.83-102 |
| issn | 0304-3975 1879-2294 |
| language | eng |
| recordid | cdi_proquest_miscellaneous_27870964 |
| source | ScienceDirect Freedom Collection 2022-2024 |
| subjects | Algebra Algorithmics. Computability. Computer arithmetics Applied sciences Combinatorics Combinatorics. Ordered structures Computer science control theory systems Exact sciences and technology General algebraic systems Graph theory Mathematical programming Mathematics Operational research and scientific management Operational research. Management science Sciences and techniques of general use Theoretical computing |
| title | A fully dynamic algorithm for distributed shortest paths |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-03T22%3A18%3A15IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20fully%20dynamic%20algorithm%20for%20distributed%20shortest%20paths&rft.jtitle=Theoretical%20computer%20science&rft.au=Cicerone,%20Serafino&rft.date=2003-03-17&rft.volume=297&rft.issue=1&rft.spage=83&rft.epage=102&rft.pages=83-102&rft.issn=0304-3975&rft.eissn=1879-2294&rft.coden=TCSCDI&rft_id=info:doi/10.1016/S0304-3975(02)00619-9&rft_dat=%3Cproquest_cross%3E27870964%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c368t-84256926236f97f2eed21014067767c23b8826984b37ae5352a61d8a9d6965a13%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=27870964&rft_id=info:pmid/&rfr_iscdi=true |