A PARALLEL ALGORITHM FOR COMPUTING STEINER TREES IN STRONGLY CHORDAL GRAPHS

Authors
DAHLHAUS E
Citation
E. Dahlhaus, A PARALLEL ALGORITHM FOR COMPUTING STEINER TREES IN STRONGLY CHORDAL GRAPHS, Discrete applied mathematics, 51(1-2), 1994, pp. 47-61
Citations number
20
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
51
Issue
1-2
Year of publication
1994
Pages
47 - 61
Database
ISI
SICI code
Abstract
We present an efficient parallel algorithm for the computation of a mi nimum Steiner tree for any strongly chordal graph. The algorithm works in O(log2 n) time and uses a linear number of processors provided a s trongly perfect elimination ordering is given.