Parallel recognition and location algorithms for chordal graphs using distance matrices (Book chapter)

Nikolopoulos, Stavros D.


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
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Keywords: Parallel algorithms,Chordal graphs,Recognition,Maximal cliques,Distance matrix,Graph partition,Complexity
URI: http://olympias.lib.uoi.gr/jspui/handle/123456789/26648
Publisher: -
Book name: -
Appears in Collections:Μονογραφίες ( Κλειστές)




 Please use this identifier to cite or link to this item:
http://olympias.lib.uoi.gr/jspui/handle/123456789/26648
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.