Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2010__44_3_293_0,
author = {C\'aceres, E. N. and Song, S. W. and Szwarcfiter, J. L.},
title = {Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {293--311},
publisher = {EDP-Sciences},
volume = {44},
number = {3},
year = {2010},
doi = {10.1051/ita/2010016},
mrnumber = {2761521},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2010016/}
}
TY - JOUR AU - Cáceres, E. N. AU - Song, S. W. AU - Szwarcfiter, J. L. TI - Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2010 SP - 293 EP - 311 VL - 44 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2010016/ DO - 10.1051/ita/2010016 LA - en ID - ITA_2010__44_3_293_0 ER -
%0 Journal Article %A Cáceres, E. N. %A Song, S. W. %A Szwarcfiter, J. L. %T Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2010 %P 293-311 %V 44 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2010016/ %R 10.1051/ita/2010016 %G en %F ITA_2010__44_3_293_0
Cáceres, E. N.; Song, S. W.; Szwarcfiter, J. L. Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 3, pp. 293-311. doi: 10.1051/ita/2010016
Cité par Sources :