A Parallel Algorithm to Test Chordality of Graphs

Agnieszka Lupinska
Uniwersytet Jagiellonski, Wydzial Matematyki i Informatyki
arXiv:1508.06329 [cs.DC], (25 Aug 2015)

   title={A Parallel Algorithm to Test Chordality of Graphs},

   author={Lupinska, Agnieszka},






Download Download (PDF)   View View   Source Source   



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.
VN:F [1.9.22_1171]
Rating: 5.0/5 (1 vote cast)
A Parallel Algorithm to Test Chordality of Graphs, 5.0 out of 5 based on 1 rating

* * *

* * *

TwitterAPIExchange Object
    [oauth_access_token:TwitterAPIExchange:private] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
    [oauth_access_token_secret:TwitterAPIExchange:private] => o29ji3VLVmB6jASMqY8G7QZDCrdFmoTvCDNNUlb7s
    [consumer_key:TwitterAPIExchange:private] => TdQb63pho0ak9VevwMWpEgXAE
    [consumer_secret:TwitterAPIExchange:private] => Uq4rWz7nUnH1y6ab6uQ9xMk0KLcDrmckneEMdlq6G5E0jlQCFx
    [postfields:TwitterAPIExchange:private] => 
    [getfield:TwitterAPIExchange:private] => ?cursor=-1&screen_name=hgpu&skip_status=true&include_user_entities=false
    [oauth:protected] => Array
            [oauth_consumer_key] => TdQb63pho0ak9VevwMWpEgXAE
            [oauth_nonce] => 1477558270
            [oauth_signature_method] => HMAC-SHA1
            [oauth_token] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
            [oauth_timestamp] => 1477558270
            [oauth_version] => 1.0
            [cursor] => -1
            [screen_name] => hgpu
            [skip_status] => true
            [include_user_entities] => false
            [oauth_signature] => 9No95mfnXiwxnPek3hhgNjdkNkU=

    [url] => https://api.twitter.com/1.1/users/show.json
Follow us on Facebook
Follow us on Twitter

HGPU group

2035 peoples are following HGPU @twitter

HGPU group © 2010-2016 hgpu.org

All rights belong to the respective authors

Contact us: