1. Repository of OAI
  2. ΑΠΟΘΕΤΗΡΙΟ "ΟΛΥΜΠΙΑΣ"
  3. Σχολή Θετικών Επιστημών
  4. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
  5. Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)
Ελληνικά   English  
Please use this identifier to cite or link to this item: https://olympias.lib.uoi.gr/jspui/handle/123456789/10972
Full metadata record
DC FieldValueLanguage
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.typejournalArticle-
heal.type.enJournal articleen
heal.type.elΆρθρο Περιοδικούel
heal.identifier.primaryDoi 10.1137/070693217-
heal.languageen-
heal.accesscampus-
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικήςel
heal.publicationDate2008-
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.journalNameSiam Journal on Computingen
heal.journalTypepeer reviewed-
heal.fullTextAvailabilityTRUE-
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Show simple item record
Files in This Item:
File Description SizeFormat 
georgiadis-2008-Linear-Time Pointer-Machine Algorithms for Path-Evaluation.pdf364.56 kBAdobe PDFView/Open
Show simple item record  


This item is licensed under a Creative Commons License Creative Commons