A Parallel Algorithm to Test Chordality of Graphs

2015/08/25 by Agnieszka Łupińska, Lupinska, Agnieszka
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Graph Theory and Algorithms #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1508.06329

openalex publication_date 2015/08/25 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We present a simple parallel algorithm to test chordality of graphs which is based on the parallel Lexicographical Breadth-First Search algorithm. In total, the algorithm takes time O(N ) on N-threads machine and it performs work O(N 2 ) , where N is the number of vertices in a graph. Our implementation of the algorithm uses a GPU environment Nvidia CUDA C. The algorithm is implemented in CUDA 4.2 and it has been tested on Nvidia GeForce GTX 560 Ti of compute capability 2.1. At the end of the thesis we present the results achieved by our implementation and compare them with the results achieved by the sequential algorithm

Related

• A GPU-based parallel algorithm for enumerating all chordless cycles in graphs
• Computing Treewidth on the GPU
• Using Graph Properties to Speed-up GPU-based Graph Traversal: A Model-driven Approach
• Optimizations to the Parallel Breath First Search on Distributed Memory
• Parallel Distributed Breadth First Search on the Kepler Architecture