IEICE TRANSACTIONS on Fundamentals
Parallel Algorithms for Maximal Linear Forests
Summary :
The maximal linear forest problem is to find, given a graph G = (V, E), a maximal subset of V that induces a linear forest. Three parallel algorithms for this problem are presented. The first one is randomized and runs in O(log n) expected time using n2 processors on a CRCW PRAM. The second one is deterministic and runs in O(log 2n) timeusing n4 processors on an EREW PRAM. The last one is deterministic and runs in O(log 5n) time using n3 processors on an EREW PRAM. The results put the problem in the class NC.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.4 pp.627-634
- Publication Date
- 1997/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ryuhei UEHARA, Zhi-Zhong CHEN, "Parallel Algorithms for Maximal Linear Forests" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 4, pp. 627-634, April 1997, doi: .
Abstract: The maximal linear forest problem is to find, given a graph G = (V, E), a maximal subset of V that induces a linear forest. Three parallel algorithms for this problem are presented. The first one is randomized and runs in O(log n) expected time using n2 processors on a CRCW PRAM. The second one is deterministic and runs in O(log 2n) timeusing n4 processors on an EREW PRAM. The last one is deterministic and runs in O(log 5n) time using n3 processors on an EREW PRAM. The results put the problem in the class NC.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_4_627/_p
Copy
@ARTICLE{e80-a_4_627,
author={Ryuhei UEHARA, Zhi-Zhong CHEN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Parallel Algorithms for Maximal Linear Forests},
year={1997},
volume={E80-A},
number={4},
pages={627-634},
abstract={The maximal linear forest problem is to find, given a graph G = (V, E), a maximal subset of V that induces a linear forest. Three parallel algorithms for this problem are presented. The first one is randomized and runs in O(log n) expected time using n2 processors on a CRCW PRAM. The second one is deterministic and runs in O(log 2n) timeusing n4 processors on an EREW PRAM. The last one is deterministic and runs in O(log 5n) time using n3 processors on an EREW PRAM. The results put the problem in the class NC.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Parallel Algorithms for Maximal Linear Forests
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 627
EP - 634
AU - Ryuhei UEHARA
AU - Zhi-Zhong CHEN
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1997
AB - The maximal linear forest problem is to find, given a graph G = (V, E), a maximal subset of V that induces a linear forest. Three parallel algorithms for this problem are presented. The first one is randomized and runs in O(log n) expected time using n2 processors on a CRCW PRAM. The second one is deterministic and runs in O(log 2n) timeusing n4 processors on an EREW PRAM. The last one is deterministic and runs in O(log 5n) time using n3 processors on an EREW PRAM. The results put the problem in the class NC.
ER -
English
