Parallel recognition and location algorithms for chordal graphs using distance matrices
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, Stavros D.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
-
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
-
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We present efficient parallel algorithms for recognizing chordal graphs and locating all maximal cliques of a chordal graph G=(V,E). Our techniques are based on partitioning the vertex set V using information contained in the distance matrix of the graph. We use these properties to formulate parallel algorithms which, given a graph G=(V,E) and its adjacency-level sets, decide whether or not G is a chordal graph, and, if so, locate all maximal cliques of the graph in time 0(k) by using 62»n2/k processors on a CRCW-PRAM, where δ is the maximum degree of a vertex in G and 1 <k<n. The construction of the adjacency-level sets can be done by computing first the distance matrix of the graph, in time O(logn) with 0(nP+DG) processors, where DG is the output size of the partitions and β=2.376, and then extracting all necessary set information. Hence, the overall time and processor complexity of both algorithms are CXlogn) and 0(max{62*n2/Zogn, nP+D0}), respectively. These results imply that, for 6<VnZogn, the proposed algorithms improve in performance upon the best-known algorithms for these problems.
Περιγραφή
Λέξεις-κλειδιά
Parallel algorithms, Chordal graphs, Recognition, Maximal cliques, Distance matrix, Graph partition, Complexity
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
349-358 σ.
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 357-358