Parallel Computation of Perfect Elimination Schemes Using Partition Techniques on Triangulated Graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Danielopoulos, S. D.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Computers & Mathematics with Applications
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Perfect elimination schemes (p.e.s.) occur in a number of important problems such as perfect Gaussian elimination. The main objective of this paper is to study the parallel computation of p.e.s, of a triangulated or perfect elimination graph G = (V, E), with n = /V/ vertices. We start with the notion of partitioning a triangulated graph into a set of (mutually disjoint) adjacency-level sets and we present a parallel algorithm, based mainly on the properties of the adjacency-level sets, which computes a p.e.s. in time O(log L . log H) using L . H . n(2) processors on a CRCW-PRAM. The computation of the adjacency-level sets of a triangulated graph can be done in time O(log L) with L . H . n(2) processors within the same type of computational model. Here, L < n and H < n are the length and the height of the graph, respectively.
Περιγραφή
Λέξεις-κλειδιά
parallel algorithm, perfect elimination, graph partition, lexicographic search, triangulated graph, crcw-pram, complexity, access
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής