Header menu link for other important links
Optimal Parallel Algorithm for Finding st-Ambitus of a Planar Biconnected Graph
Swaminathan V. Krishnan, ,
Published in Springer New York
Volume: 15
Issue: 3
Pages: 242 - 255
A cycle C passing through two specific vertices s and t of a biconnected graph is said to be an st-ambitus if its bridges do not interlace in some special way. We present algorithms for st-ambitus for planar biconnected graphs, which are much simpler than the one known for general graphs [MT]. Our algorithm runs in O(n) time on a sequential machine and (log n) parallel time using O(n/log n) processors on an EREW PRAM.
About the journal
JournalData powered by TypesetAlgorithmica (New York)
PublisherData powered by TypesetSpringer New York
Open AccessNo