Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems

Απλή σελίδα τεκμηρίου
dc.contributor.authorBuchsbaum, A. L.en
dc.contributor.authorGeorgiadis, L.en
dc.contributor.authorKaplan, H.en
dc.contributor.authorRogers, A.en
dc.contributor.authorTarjan, R. E.en
dc.contributor.authorWestbrook, J. R.en
dc.date.accessioned2015-11-24T17:01:45Z
dc.date.available2015-11-24T17:01:45Z
dc.identifier.issn0097-5397-
dc.identifier.urihttps://olympias.lib.uoi.gr/jspui/handle/123456789/10972
dc.rightsDefault Licence-
dc.subjectdominatorsen
dc.subjectflowgraphsen
dc.subjectpointer machineen
dc.subjectrandom-access machineen
dc.subjectset unionen
dc.subjectpath compressionen
dc.subjectnearest common ancestorsen
dc.subjectminimum spanning treesen
dc.subjectinterval analysisen
dc.subjectcomponent treeen
dc.subjectdata structuresen
dc.subjectanalysis of algorithmsen
dc.subjectminimum spanning-treesen
dc.subjectnearest common ancestorsen
dc.subjectdisjoint set unionen
dc.subjectdependence graphen
dc.subjectshortest pathsen
dc.subjectdynamic treesen
dc.subjectverificationen
dc.subjectfinden
dc.subjectcompressionen
dc.subjectbottlenecksen
dc.titleLinear-Time Algorithms for Dominators and Other Path-Evaluation Problemsen
heal.abstractWe present linear-time algorithms for the classic problem of finding dominators in a flowgraph, and for several other problems whose solutions require evaluating a function defined on paths in a tree. Although all these problems had linear-time solutions previously, our algorithms are simpler, in some cases substantially. Our improvements come from three new ideas: a refined analysis of path compression that gives a linear bound if the compressions favor certain nodes; replacement of random-access table look-up by a radix sort; and a more careful partitioning of a tree into easily managed parts. In addition to finding dominators, our algorithms find nearest common ancestors off-line, verify and construct minimum spanning trees, do interval analysis of a flowgraph, and build the component tree of a weighted tree. Our algorithms do not require the power of a random-access machine; they run in linear time on a pointer machine. The genesis of our work was the discovery of a subtle error in the analysis of a previous allegedly linear-time algorithm for finding dominators. That algorithm was an attempt to simplify a more complicated algorithm, which itself was intended to correct errors in a yet earlier algorithm. Our work provides a systematic study of the subtleties in the dominators problem, the techniques needed to solve it in linear time, and the range of application of the resulting methods. We have tried to make our techniques as simple and as general as possible and to understand exactly how earlier approaches to the dominators problem were either incorrect or overly complicated.en
heal.accesscampus-
heal.fullTextAvailabilityTRUE-
heal.identifier.primaryDoi 10.1137/070693217-
heal.journalNameSiam Journal on Computingen
heal.journalTypepeer reviewed-
heal.languageen-
heal.publicationDate2008-
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικήςel
heal.typejournalArticle-
heal.type.elΆρθρο Περιοδικούel
heal.type.enJournal articleen

Αρχεία

Πρωτότυπος φάκελος/πακέτο

Προβολή: 1 - 1 of 1
Μικρογραφία εικόνας
Ονομα:
georgiadis-2008-Linear-Time Pointer-Machine Algorithms for Path-Evaluation.pdf
Μέγεθος:
364.56 KB
Μορφότυπο:
Adobe Portable Document Format
Κατεβάστε

Φάκελος/Πακέτο αδειών

Προβολή: 1 - 1 of 1
Μικρογραφία εικόνας
Ονομα:
license.txt
Μέγεθος:
1.74 KB
Μορφότυπο:
Item-specific license agreed upon to submission
Περιγραφή:
Κατεβάστε

Συλλογές

Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)