An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs
-
- HONMA Hirotoshi
- Department of Information Engineering, Kushiro National College of Technology
-
- HONMA Saki
- Electronic Information System Engineering Course, Kushiro National College of Technology
-
- MASUYAMA Shigeru
- Department of Knowledge-Based Information Engineering, Toyohashi University of Technology
この論文をさがす
抄録
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.
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E92-D (2), 141-148, 2009
一般社団法人 電子情報通信学会
- Tweet
詳細情報
-
- CRID
- 1390282679354457472
-
- NII論文ID
- 10026807322
-
- NII書誌ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可