IEICE TRANSACTIONS on Information
An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs
Summary :
The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.
- Publication
- IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.141-148
- Publication Date
- 2009/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E92.D.141
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- 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
Hirotoshi HONMA, Saki HONMA, Shigeru MASUYAMA, "An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 141-148, February 2009, doi: 10.1587/transinf.E92.D.141.
Abstract: The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.141/_p
Copy
@ARTICLE{e92-d_2_141,
author={Hirotoshi HONMA, Saki HONMA, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs},
year={2009},
volume={E92-D},
number={2},
pages={141-148},
abstract={The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.},
keywords={},
doi={10.1587/transinf.E92.D.141},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 141
EP - 148
AU - Hirotoshi HONMA
AU - Saki HONMA
AU - Shigeru MASUYAMA
PY - 2009
DO - 10.1587/transinf.E92.D.141
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.
ER -
English
