Issue |
RAIRO-Theor. Inf. Appl.
Volume 44, Number 3, July-September 2010
|
|
---|---|---|
Page(s) | 293 - 311 | |
DOI | https://doi.org/10.1051/ita/2010016 | |
Published online | 23 June 2010 |
Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search
1
Universidade Federal de Mato Grosso do Sul,
Faculdade de Computação,
79070-900 Campo Grande, MS, Brazil; edson@facom.ufms.br
2
Universidade de São Paulo, Instituto de Matemática e Estatística,
05508-900 São Paulo, SP, Brazil; visiting professor of Universidade Federal do ABC;
song@ime.usp.br
3
Universidade Federal do Rio de Janeiro,
Instituto de Matemática, Núcleo de Computação Eletrônica
and COPPE,
21.945-970 Rio de Janeiro, RJ, Brazil;
jayme@nce.ufrj.br
Received:
30
March
2009
Accepted:
2
June
2010
We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O log (p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.
Mathematics Subject Classification: 68W10 / 05C85 / 05C69
Key words: BSP/CGM algorithm / PRAM algorithm / circle graph / maximal clique / unrestricted depth search.
© EDP Sciences, 2010
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.