Parallel recognition and location algorithms for chordal graphs using distance matrices
| dc.contributor.author | Nikolopoulos, Stavros D. | en |
| dc.date.accessioned | 2015-12-11T13:06:07Z | |
| dc.date.available | 2015-12-11T13:06:07Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/26648 | |
| dc.rights | Default License | |
| dc.subject | Parallel algorithms | en |
| dc.subject | Chordal graphs | en |
| dc.subject | Recognition | en |
| dc.subject | Maximal cliques | en |
| dc.subject | Distance matrix | en |
| dc.subject | Graph partition | en |
| dc.subject | Complexity | en |
| dc.title | Parallel recognition and location algorithms for chordal graphs using distance matrices | en |
| heal.abstract | 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 |
| heal.access | campus | |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 357-358 | el |
| heal.bookName | - | en |
| heal.fullTextAvailability | true | |
| heal.generalDescription | 349-358 σ. | el |
| heal.language | en | |
| heal.publicationDate | 1994 | |
| heal.publisher | - | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.type | bookChapter | |
| heal.type.el | Κεφάλαιο βιβλίου | el |
| heal.type.en | Book chapter | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: