Name
Title | ||
|---|---|---|
A Linear-Time Algorithm For Constructing A Spanning Tree On Circular Trapezoid Graphs |
Abstract | ||
|---|---|---|
Given a simple connected graph G with n vertices, the spanning tree problem involves finding a tree that connects all the vertices of G. Solutions to this problem have applications in electrical power provision, computer network design, circuit analysis, among others. It is known that highly efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper super-classes of trapezoid graphs. In this paper, we propose an O(n) time algorithm for the spanning tree problem on a circular trapezoid graph: Moreover, this algorithm can be implemented in O(log n) time with O(n/ log n) processors on EREW PRAM computation model. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1587/transfun.E96.A.1051 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
design and analysis of algorithms, intersection graphs, circular trapezoid graphs, spanning tree problem | Discrete mathematics,Combinatorics,Indifference graph,Minimum degree spanning tree,k-minimum spanning tree,Chordal graph,Spanning tree,Time complexity,Trapezoid graph,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
E96A | 6 | 1745-1337 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hirotoshi Honma | 1 | 30 | 9.77 |
| Yoko Nakajima | 2 | 1 | 0.70 |
| Haruka Aoshima | 3 | 0 | 0.34 |
| Shigeru Masuyama | 4 | 107 | 28.06 |