δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Parallel recognition and location algorithms for chordal graphs using distance matrices
(EN)
Nikolopoulos, Stavros D.
(EN)
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
(EL)
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.
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Πανεπιστήμιο Ιωαννίνων
