An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs

Hirotoshi Honma, Yoko Nakajima, Shino Nagasaki, Atsushi Sasaki

National Institute of Technology, Kushiro College, Kushiro, Japan.

DOI: 10.4236/jamp.2018.68141                

Abstract

Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.

Keywords

Design and Analysis of Parallel Algorithms, Proper Circle Trapezoid Graphs, Spanning Tree

1. Introduction

Given a simple connected graph G with n vertices, the spanning tree problem is to find a tree that connects all the vertices of G. The spanning tree problem has applications, such as electric power systems, computer network design and circuit analysis [1] . A spanning tree can be found in $O\left(n+m\right)$ time using, for example, the depth-first search or breadth-first search. In recent years, a large number of studies have been made to parallelize known sequential algorithms. For simple graphs, Chin et al. presented that the spanning forest can be found in $O\left(lo{g}^{2}n\right)$ time using $O\left(n{}^2/lo{g}^{2}n\right)$ processors [2] . Moreover, for a connected graph, Klein and Stein demonstrated that a spanning tree can be found in $O\left(logn\right)$ time with $O\left(n+m\right)$ processors on the CRCW (Concurrent Read Concurrent Write) PRAM (Parallel Random Access Machine) [3] .

In general, it is known that more efficient algorithms can be developed by restricting classes of graphs. For instance, Wang et al. proposed an optimal parallel algorithm for constructing a spanning tree on permutation graphs that run in $O\left(logn\right)$ time using $O\left(n/logn\right)$ processors on the EREW (Exclusive Read Exclusive Write) PRAM [4] . Wang et al. proposed optimal parallel algorithms for some problems including the spanning tree problem on interval graphs that can be executed in $O\left(logn\right)$ time with $O\left(n/logn\right)$ processors on the EREW PRAM [5] . Bera et al. presented an optimal parallel algorithm for finding a spanning tree on trapezoid graphs that take in $O\left(logn\right)$ time using $O\left(n/logn\right)$ processors on the EREW PRAM [6] . In addition, Honma et al. developed parallel algorithms for finding a spanning tree on circular permutation graphs [7] and circular trapezoid graphs [8] . Both of them take in $O\left(logn\right)$ time using $O\left(n/logn\right)$ processors on the EREW PRAM.

Felsner et al. first introduced circle trapezoid graphs [9] . They also provided an $O\left(n^2\right)$ time algorithm for solving maximum independent set problem and $O\left(n^{2}logn\right)$ time algorithm for solving maximum clique problem. Recently, Lin showed that circle trapezoid graphs are superclasses of trapezoid graphs [10] .

In this study, we propose a parallel algorithm for spanning tree problem on a proper circle trapezoid graph. It can run in $O\left(logn\right)$ time with $O\left(n/logn\right)$ processors on the EREW PRAM. The rest of this paper is organized as follows. Section 2 describes some definitions of circle trapezoid graphs and models and introduces the extended circle trapezoid model, as well as some notation. Section 3 presents some properties on circle trapezoid graphs, which are useful for finding a spanning tree in an efficient manner. Section 4 describes our parallel algorithm for the spanning tree problem and its complexity. Finally, Section 5 concludes the paper.

2. Preliminaries

2.1. Circle Trapezoid Model and Graph

We first illustrate the circle trapezoid model before defining the circle trapezoid graph. There is a unit circle C such that the consecutive integer i, $1\le i\le 4n$ are assigned clockwise on the circumference (n is the number of circle trapezoids). Consider nonintersecting two arcs $A^{\prime }=\left[a_i{b}_i\right]$ and $A^{″}=\left[c_i{d}_i\right]$ along the circumference of C. The point $b_i$ (resp., $d_i$ ) is the last point encountered when traversing $A^{\prime }$ (resp., $A^{″}$ ) clockwise. A circle trapezoid $C{T}_i$ is the region in a circle C that lies between two non-crossing chords $\langle a_i{d}_i\rangle$ and $\langle b_i{c}_i\rangle$ . Without loss of generality, each circle trapezoid $C{T}_i$ has four corner points $a_i,b_i,c_i,d_i$ , and all corner points are distinct. We assume that circle trapezoids are labeled in increasing order of their corner points $a_i$ ’s, i.e., $C{T}_i<C{T}_j$ if $a_i<a_j$ . The geometric representation described above is called the circle trapezoid model. Figure 1(a) illustrates an example of a circle trapezoid model M with eight circle trapezoids. The circle trapezoid with $a_i>d_i$ is called feedback circle trapezoid. Note that there exist two feedback circle trapezoids ( $C{T}_7\mathrm{,}C{T}_8$ ) in a circle trapezoid model M.

An undirected graph G is a circle trapezoid graph if it can be represented by the following circle trapezoid model; each vertex of the graph corresponds to a circle trapezoid in circle trapezoid model, and two vertices are adjacent in G if and only if their circle trapezoids intersect [9] . Figure 1(b) illustrates a circle trapezoid graph G corresponding to M shown in Figure 1(a). Table 1 shows the details of circle trapezoid model M of Figure 1.

2.2. Extended Circle Trapezoid Model

In the following, we introduce the extended circle trapezoid model EM constructed from a circle trapezoid model for making the problem easier. We first cut a circle trapezoid model M at point 1 on the circumference and next unroll onto the real horizontal line. Each circle trapezoid $C{T}_i=\left[a_i,b_i,c_i,d_i\right]$ in M is also changed to a pair of line segment $I_i=\left(\left[a_i\mathrm{,}{d}_i\right]\mathrm{,}\left[b_i\mathrm{,}{d}_i\right]\right)$ called interval pair by executing the above process. Here, feedback circle trapezoid $C{T}_i=\left[a_i,b_i,c_i,d_i\right]$ in M is changed to interval pair $I_i=\left(\left[a_i,d_i+4n\right],\left[b_i+4n,d_i+4n\right]\right)$ for $a_i>b_i,c_i,d_i$ . Moreover, copies $I_{i-n}$ of $I_i$ are created by shifting 4n to the left respectively, for each $I_i$ , $1\le i\le n$ . Note that both interval pairs $I_i$ and $I_{i-n}$ in extended circle trapezoid model EM are corresponding to $C{T}_i$ in M.

The following Algorithm CEM constructs an EM from a M. Figure 2 shows the EM constructed from the M illustrated in Figure 1. Table 2 shows the details of EM of Figure 2.

Algorithm CEM

Input: Corner points $\left[a_i\mathrm{,}{b}_i\mathrm{,}{c}_i\mathrm{,}{d}_i\right]$ of $C{T}_i$ in M.

Begin

For each non feedback circle trapezoid $C{T}_i$ pardo

Create a interval pair $I_i=\left(\left[a_i,d_i\right],\left[b_i,d_i\right]\right)$ ;

For each feedback circle trapezoid $C{T}_i$ pardo

For each $b_i,c_i,d_i<a_i$

Create a interval pair $I_i=\left(\left[a_i,d_i+4n\right],\left[b_i+4n,d_i+4n\right]\right)$ ;

For $1\le i\le n$ pardo

Create copies $I_{i-n}$ by shifting 4n to the left for $I_i$ ;

End

3. Proper Circle Trapezoid Model and Graph

3.1. Definitions for Proper Circle Trapezoid Graph

In this study, we focus and treat a proper circle trapezoid graph. Graph G is a circle trapezoid graph corresponding to a circle trapezoid model M and an extended circle trapezoid model EM is constructed from M by executing Algorithm CEM. We consider circle trapezoid model M such that the extended

Figure 1. Circle trapezoid model and graph. (a) Circle trapezoid model M; (b) Circle trapezoid graph G.

Figure 2. Extended circle trapezoid model EM.

Table 1. Details of circle trapezoid model M.

Table 2. Details of extended circle trapezoid model EM.

circle trapezoid model EM constructed from M satisfies that $c_i<d_j$ for two interval pairs $I_i$ and $I_j$ $\left(i<j\right)$ in EM. The circle trapezoid model $M_p$ is defined as proper circle trapezoid model. The graph corresponding to the proper circle trapezoid model is proper circle trapezoid graph $G_p$ . In this study, we will develop a parallel algorithm for spanning tree problem on proper circle trapezoid graphs. The Figure 1 is also an example of $M_p$ and $G_p$ because $c_i<d_j$ for $I_i$ and $I_j$ $\left(i<j\right)$ in extended circle trapezoid model EM.

Here, some notations that form the basis of our algorithm are defined as follows.

The function $\text{nor}\left(i\right)$ normalizes the interval pair number i in EM within the range 1 to n, which is expressed as

$\text{nor}\left(i\right)=\{\begin{array}{ll}i\hfill & \text{if}i\ge \text{1,}\hfill \\ i+n\hfill & \text{if}i<\text{1}\text{.}\hfill \end{array}$

For the example shown in Figure 2, for $i=4$ and $i=-5$ , we have $\text{nor}\left(4\right)=4$ and $v\left(-5\right)=3$ , respectively.

The function $v_d\left(k\right)$ computes a vertex number i satisfying $d_i=k$ for a given number k on EM. For the example shown in Figure 2, for $k=29$ and $k=-13$ , we have $v_d\left(29\right)=5$ and $v_d\left(-13\right)=-6$ by $d_5=29$ and $d_{-6}=-13$ , respectively. Moreover, we use $n{v}_d\left(k\right)$ instead of $\text{nor}\left(v_d\left(k\right)\right)$ for simplicity. For the example shown in Figure 2, for $k=29$ and $k=-13$ , we have $n{v}_d\left(29\right)=5$ and $n{v}_d\left(-13\right)=2$ by $v_d\left(29\right)=5$ and $v_d\left(-13\right)=-6$ , respectively.

We next define $l{d}_i=\max \left\{d_{-n+1},d_{-n+2},\cdots ,d_i\right\}$ , for $-n+1\le i\le n-1$ , in $E{M}_p$ . The details of $l{d}_i$ , $v_d\left(d_i\right)$ , and $n{v}_d\left(d_i\right)$ are shown in Table 3.

3.2. Property of Proper Circle Trapezoid Graph

We describe some properties on circle trapezoid graphs which are useful for constructing the algorithm for spanning tree problem on proper circle trapezoid graphs.

For two interval pairs $I_i$ and $I_j$ $\left(i<j\right)$ in EM, we say $I_i$ and $I_j$ are disjoint if $d_i<a_j$ . Moreover, we say $I_i$ contain $I_j$ if and. Figure 3 shows examples of the cases of disjoint and contain. The following Lemma 1 has been described in [9] .

Table 3. Details of extended circle trapezoid model EM.

Figure 3. Examples of disjoint and contain. (a) and are disjoint (); (b) contains (and).

Lemma 1 Let and be non-feedback circle trapezoids in circle trapezoid model M. Moreover, extended circle trapezoid model EM is constructed from M. and intersect if and are not disjoint and does not contain in EM.

The following Lemma 2 generalizes Lemma 1. This is very useful to find the edges on circle trapezoid graph.

Lemma 2 G is a circle trapezoid graph corresponding to a circle trapezoid model M, and extended circle trapezoid model EM is constructed from M. For two interval pairs , an edge is in G if and only if at least one of the following conditions satisfies in EM;

1),

2) and.

(Proof) By Lemma 1, for two non-feedback circle trapezoids and do not intersect if and only if () or (and) in EM. By the contra position, for two non-feedback circle trapezoids and intersect if and only if () and (or) in EM. Here, () and (or) is logically equal to (and) or (and).

For the condition () and (), we have whenever. Thus, is an edge of CTG G if () or (and) for two interval pairs and in EM. □

We obtain the following Lemma 3 for a proper circle trapezoid model and graph.

Lemma 3. is a proper circle trapezoid graph corresponding to a proper circle trapezoid model, and is an extended circle trapezoid model constructed from. An edge is in if and only if for satisfies in the.

(Proof) By Lemma 2, if either of conditions 1) () or 2) (and) for two interval pairs and in, an edge is in. By definition of proper circle trapezoid graph, we have in. Hence, condition 2) satisfies when holds. Moreover, condition 1) satisfies if holds because by the definition of interval pair. Therefore an edge is in if and only if for satisfies in the. □

In Lemma 2, we have to test if or (and) in EM to check whether is an edge of normal circle trapezoid graph G. On the other hand, by Lemma 3, we only need to check holds for to determine whether an edge is in proper circle trapezoid graph.

The following Lemma 4 is core of solving this problem. An efficient algorithm can be constructed by using the following lemma.

Lemma 4. is a proper circle trapezoid graph corresponding to an, and is an extended circle trapezoid model constructed from. For, an edge is in if satisfies in the.

(Proof) By the definition,. Thus, we have. By Lemma 3, an edge is in if and only if for. Therefore, an edge is in if satisfies in the. □

4. Parallel Algorithm

In this section, we propose an algorithm for constructing a spanning tree of a connected proper circle trapezoid graph. We assume that all trapezoids in the proper circle trapezoid model have been sorted by corner point a in ascending order, that is, Table 1 is given as an input of our algorithm. Algorithm CST returns a spanning tree if a given graph is connected. Instead of using a sophisticated technique, we propose simple parallel algorithms using only the parallel prefix computation [11] and Brent’s scheduling principle [12] .

Algorithm CST

Input: and,.

Output: A spanning forest F of G. Initially F be an empty set.

Begin

(Step 1) % Initializing

;

For i, pardo

;

For i, pardo

;

(Step 2) % Computing

For i, pardo

;

;

For i, pardo

;

For i, pardo

;

(Step 3) % Construct a spanning forest

For i, pardo

If

then;

End

Lemma 5. After executing Step 3 of Algorithm CST, graph T is a spanning tree of proper circle trapezoid graph.

(Proof) Step 1 is a process for initialization. T is empty set and all are set to “0”. For all, compute using parallel prefix computation [11] .

In Step 2, we set, , if. In addition, we compute. By Lemma 4, an edge is in if. Thus, a vertex i that can have least one edge from i to other vertex. Vertex s is the largest satisfying. For the example shown in Figure 4, we set because, for. For the only case of, we have then.

We consider that T is added an edge form i to smaller for i,. By definitions of and ld, if corresponds a copy of a non-feedback circle trapezoid, we have. On the other hand, if corresponds a copy of a feedback circle trapezoid, we have. In the case of, T constructed in above way is connected graph that has n vertices. Thus, T is not a tree that has exactly one cycle C. There exist some edge in C such that is feedback circle trapezoid, because a given is connected. In Step 2, we obtained. In not adding to T, we can remove a cycle C.

Figure 4. Example of constructed spanning tree.

In Step 3, in the case of, we add an edge to T for vertex i, ,. T is connected with vertices, that is, T is a tree. In Step 3, we consider the case of. This implies. If, this means that a given is disconnected, which is a contradiction to our hypothesis. Therefore, in the case of, we add an edge to T for vertex i, ,. T is connected with vertices, that is, T is a tree.

Therefore, after executing Step 3 of Algorithm CST, graph T is a spanning tree of proper circle trapezoid graph. □

Figure 4 shows a spanning tree T constructed from CTG by executing Algorithm CST.

In the following, we analyze the complexity of Algorithm CST.

In Step 1, an extended circle trapezoid model is constructed from a circle trapezoid model in time using processors, which can be implemented in time using processors by applying Brent’s scheduling principle [12] . Moreover, all are obtained in time using processors by applying parallel prefix computation [11] . In Step 2, and s are computed in time using processors by applying Brent’s scheduling principle. Step 3 can also be implemented in time using processors by applying Brent’s scheduling principle. In addition, Algorithm CST can be executed on an EREW PRAM because neither concurrent read nor concurrent write are necessary. Thus, we have the subsequent theorem.

Theorem 6. Algorithm CST constructs a spanning tree of a proper circle trapezoid graph in time using processors on EREW PRAM. □

5. Concluding Remarks

In this paper, we presented a parallel algorithm to solve the spanning tree problem on a proper circle trapezoid graph. This algorithm can be implemented in time with processors on an EREW PRAM computation model using only parallel prefix computation [11] and Brent’s scheduling principle [12] without using a sophisticated technique. Solutions to the spanning problem have applications in electrical power provision, computer network design, and circuit analysis, among others. For this reason, we think this paper is also worthy from both a theoretical and algorithmic point of view. In the future, we will continue this research by extending the results to other classes of graphs.

Acknowledgements

We express many thanks to anonymous referees for their valuable advices on the theory of our attacks and their helpful editorial comments. This work was supported by JSPS KAKENHI Grant Number 17K00324 and 17K04965.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Wilson, R.J. (1996) Introduction to Graph Theory. Prentice Hall, Upper Saddle River.
[2]	Chin, F.Y., Lam, J. and Chen, I. (1982) Efficient Parallel Algorithms for Some Graph Problems. Communications of the ACM, 25, 659-665. https://doi.org/10.1145/358628.358650
[3]	Klein, P. and Stein, C. (1990) A Parallel Algorithm for Eliminating Cycle in Undirected Graphs. Information Processing Letters, 34, 307-312. https://doi.org/10.1016/0020-0190(90)90015-P
[4]	Wang, Y. L., Chen, H. C. and Lee, C. Y. (1995) An Parallel Algorithm for Constructing a Spanning Tree on Permutation Graphs. Information Processing Letters, 56, 83-87. https://doi.org/10.1016/0020-0190(95)00125-V
[5]	Wang, Y. L., Chiang, K. C. and Yu, M. S. (1998) Optimal Algorithms for Interval Graphs. Journal of Information Science and Engineering, 14, 449-459.
[6]	Bera, D., Pal, M. and Pal, T. K. (2003) An Optimal PRAM Algorithm for a Spanning Tree on Trapezoid Graphs. Journal of Applied Mathematics and Computing, 1-2, 21-29. https://doi.org/10.1007/BF02936178
[7]	Honma, H., Honma, S. and Masuyama, S. (2009) An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs. IEICE Transactions on Information and Systems, E92-D, 141-148. https://doi.org/10.1587/transinf.E92.D.141
[8]	Honma, H., Nakajima, Y., Igarashi, Y. and Masuyama, S. (2014) Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs. IEICE Transactions on Fundamentals of Electronics, E97-A, 1365-1369. https://doi.org/10.1587/transfun.E97.A.1365
[9]	Felsner, S., Müller, R. and Wernisch, L. (1997) Trapezoid Graphs and Generalization, Geometry and Algorithms. Discrete Applied Mathematics, 74, 13-32. https://doi.org/10.1016/S0166-218X(96)00013-3
[10]	Lin, W. L. (2006) Circular and Circle Trapezoid Graphs. Journal of Science and Engineering Technology, 2, 11-17.
[11]	Gibbons, A. and Rytter, W. (1988) Efficient Parallel Algorithms. Cambridge University Press, Cambridge.
[12]	Brent, R. P. (1974) The Parallel Evaluation of General Arithmetic Expressions. Journal of the ACM, 21, 201-206. https://doi.org/10.1145/321812.321815