An efficient NC algorithm for a sparse k-edge-connectivity certificate

Authors
Nagamochi, H Hasunuma, T
Citation
H. Nagamochi et T. Hasunuma, An efficient NC algorithm for a sparse k-edge-connectivity certificate, J ALGORITHM, 38(2), 2001, pp. 354-373
Citations number
12
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF ALGORITHMS
ISSN journal
01966774 → ACNP
Volume
38
Issue
2
Year of publication
2001
Pages
354 - 373
Database
ISI
SICI code
0196-6774(200102)38:2<354:AENAFA>2.0.ZU;2-5
Abstract
We present an efficient NG algorithm for finding a sparse k-edge-connectivi ty certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)(2 )(log n)(2)) time using O(k(n + m')) processors on an ARBITRARY CRCW PRAM, where n. and m' stand for the numbers of vertices in G and edges in the sim plified graph of G, respectively. (C) 2001 Academic Press.