An optimal parallel algorithm for computing cut vertices and blocks on interval graphs

Authors
Pal, M Mondal, S Bera, D Pal, TK
Citation
M. Pal et al., An optimal parallel algorithm for computing cut vertices and blocks on interval graphs, INT J COM M, 75(1), 2000, pp. 59-70
Citations number
15
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
ISSN journal
00207160 → ACNP
Volume
75
Issue
1
Year of publication
2000
Pages
59 - 70
Database
ISI
SICI code
Abstract
In this paper, a parallel algorithm is presented to find ail cut-vertices a nd blocks of an interval graph. If the list of sorted end points of the int ervals of an interval graph is given then the proposed algorithm takes O(lo g n) time acid O(n/log n) processors on an EREW PRAM, if the sorted list is not given then the time and processors complexities are respectively O(log n) and O(n).