DSpace
 

EPrints@IIT Delhi >
Faculty Research Publicatons  >
Computer Science and Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/1498

Full metadata record

DC FieldValueLanguage
dc.contributor.authorBaswana, Surender-
dc.contributor.authorHariharan, Ramesh-
dc.contributor.authorSen, Sandeep-
dc.date.accessioned2006-03-23T06:48:27Z-
dc.date.available2006-03-23T06:48:27Z-
dc.date.issued2004-
dc.identifier.citationJournal of Algorithms, In Press, Corrected Proofen
dc.identifier.urihttp://eprint.iitd.ac.in/dspace/handle/2074/1498-
dc.description.abstractThis paper presents improved algorithms for the following problem: given an unweighted directed graph G(V,E) and a sequence of on-line shortest-path/reachability queries interspersed with edge-deletions, develop a data-structure that can answer each query in optimal time, and can be updated efficiently after each edge-deletion. The central idea underlying our algorithms is a scheme for implicitly storing all-pairs reachability/shortest-path information, and an efficient way to maintain this information. Our algorithms are randomized and have one-sided inverse polynomial error for query.en
dc.format.extent893397 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoenen
dc.subjectBFS treeen
dc.subjectDynamicen
dc.subjectGraphen
dc.subjectTransitive closureen
dc.subjectShortest pathsen
dc.titleImproved decremental algorithms for maintaining transitive closure and all-pairs shortest pathsen
dc.typeArticleen
Appears in Collections:Computer Science and Engineering

Files in This Item:

File Description SizeFormat
baswanaimp2004.pdf872.46 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback