数理解析研究所講究録1093 巻 1999 年 27-32

27Tractable and Intractable Problems on Generalized Chordal Graphs*
上原隆平 (Ryuhei Uehara)jp$\mathrm{u}\mathrm{e}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{Q}\mathrm{k}_{0}\mathrm{m}\mathrm{a}\mathrm{Z}\mathrm{a}\mathrm{w}\mathrm{a}-\mathrm{u}.\mathrm{a}\mathrm{c}.$Faculty of Natural Sciences, Komazawa University

Abstract

Key words: Generalized chordal graph, maximal acyclic subgraph, NC
algorithm, RNC algorithm, NPcomplete problem,-complete problem.
$\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$1

Introduction

A chordal graph is the graph whose each cycleof length greater than 3 has a chord. Chordal
graphs have applications in Gaussian elimination anddatabases and have been the object of much algorithmic study. On the other hand, chordal graphs arealso important from the graph theoretical point ofview. The class of chordal graphs is subclass of theclass of perfect graphs, and superclass the class ofinterval graphs (see [17, 12] for details). It is natural to generalize about the length of the cycle on thechordal graph. We introduce a notion of a k-chordal
graph whose each cycle of length greater than has
a chord. An ordinary chordal graph is a 3-chordal
graph, and so-called chordal bipartite graph can be
defined by a bipartite 4-chordal graph. In this paper,
we consider the complexities of the recognition problem for -chordalness, and some graph problems on
a -chordal graph.
We first consider the case that is a fixed positive integer. We extend the characterization of a 3chordal graph by Edenbrandt [8] in a nontrivial way,
and show that the recognition problem of a k-chordal
graph is in NC for any fixed . We modify the NC algorithm, and show that the bipartite -chordal graphalso can be recognized in parallel. We remark thatfor a bipartite 4-chordal graph, the ordinary chordal$\mathrm{o}\mathrm{f}^{f}$

$k$

$k$

$k$

$k$

$k$

$k$

$-arrow$

bipartite graph, only polynomial time algorithms are
known (see e.g. [14, 18]).

For a fixed , we next consider the manimal acyclicset (MAS) problem on a -chordal graph. The MAS
problem is to find a maximal vertex induced acyclic
subgraph for a given graph. The MAS problem has
been solved partially; in the case that some properties
are added to the acyclicness $[19, 21]$ , and on some restricted graphs [3]. Our results are in the latter case;the problem is in NC on a 3-chordal graph, and in
RNC on a -chordal graph for any fixed $k>3$ .
We here remark that no graph has a simple cycle of length greater than , where is the numberof vertices. Hence we can regard every graph as an-chordal graph. On the other hand, there are several problems such that they are-complete on a
general graph, and they are polynomial time solvable
on a 3-chordal graph. For example, maximum independent set problem, chromatic number problem,and maximum clique problem are-complete on a
general graph [9], and they are polynomial time solvable on a 3–chordal graph [10]. (These problems areeven in NC on a 3-chordal graph $[17, 12]$ .) These
facts motivate us to consider the case of general
as a function of . We first show that the recognition problem for -chordalness is-complete for$k=\Theta(n)$ . We next show that, for any positive
con$k$

$k$

$k$

$n$

$n$

$n$

$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$

$k$

$n$

$k$

*This research was partially supported by the Ministry of Education, Science, Sports andCulture,agement of Young Scientists, 10780203, 1998.

$\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$$\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{t}- \mathrm{i}_{\mathrm{D}}$id for Encour-

28

problem on a general graphstant , any
is also-complete on a -chordal graph even for-completeness of. This also implies
the recognition problem for -chordalness even for.
$\mathrm{N}\mathrm{P}- \mathrm{c}\mathrm{o}\mathrm{m}_{\dot{\mathrm{P}}^{1}}\mathrm{e}\mathrm{t}\mathrm{e}$$\epsilon$$k$$\mathrm{N}\mathrm{P}$$k=\Theta(n^{\epsilon})$$\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$$k$$k=\Theta(n^{\epsilon})$Preliminaries

2

A graph $G=(V, E)$ consists of a finite set $V$ of vertices and a colection $E$ of 2-element subsets of, the subgraph of induced
called edges. For
by is the graph $(U, F)$ , where $F=\{\{u, v\}|\{u, v\}\in$$E$ ,and $v\in U$ }, and is denoted by $G[U]$ . We define
the neighborhood of a vertex in , denoted $N_{G}(v)$ ,by the set of vertices with $\{u, v\}\in E$ . For a set ofvertices $U,$ $N_{G}(U)$ is defined by { $v|v\in N_{G}(u)$ for $u\in$. The degree of a vertex in is $|N_{G}(v)|$ . A
graph is -regular if every vertex in has degree
is a path,. A sequence of the vertices
denoted by $(v_{0}, v_{1,l}\ldots, v)$ , if $\{v_{j},v_{j+1}\}\in E$ for each$0\leq j\leq l-1$ . The path is simple if all the vertices are distinct with each other. We say the firstand last vertices of the sequence the endpoints of thepath. The length of a path is the number of edges
on the path. A cycle is a path beginning and ending with the same vertex. A cycle is simple if all thevertices are distinct with each other except the common endpoint. A Hamiltonian cycle is a simple cyclethat visits all vertices in the graph. The Hamiltonian cycle problem is to find a Hamiltonian cycle ina given graph. A vertex set
is cyclic if there exists at least one permutationis aof size such that
simple cycle. An edge which joins two vertices of acycle but is not itself an edge of the cycle is a chord ofthat cycle. A graph is -chordal if each of its cyclesof length greater than has a chord. (An ordinary
chordal graph can be defined by a 3-chordal graph[6].) The recognition problem for -chordalness is todecide whether for a given graph and a given integer
the graph is -chordal. An acyclic set is a set ofvertices that contains no cyclic vertex set. A maximal acyclic set (MAS) of is an acyclic set that is
not properly contained in any other acyclic set of .
The MAS problem of is to find an MAS of . We
say a cyclic vertex set is minimal if $G[U]$ has nochord. We say cyclic decomposition set of $G$ , denotedby], a family of all minimal cyclic vertex set in
$V$

$G$

$U\subseteq V$$U$

A hypergraph $H=(V, E)$ consists of a finite setof vertices and a collection $E$ of non-empty subsets
ofcalled hyperedges. The dimension in $H$ is the
maximum size of a hyperedge in $E$ . An independent
set in $H$ is a subset of not containing any edge of$H$ . A maximal independent set (MIS) of $H$ is an independent set of $H$ that is not properly contained insome other independent set. The MIS problem on $H$
is to find an MIS in $H$ .
The definitions and the details of the complexity, and) and the paralclasses ( , RNC,
PRAM,
and CRCWlel computation models (EREW[13]
omitted
here.
in
and
PRAM) can be found
$V$

$V$

$V$

$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{C}$$\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$

$u,$

$G$

$v$

$u$

$U\}$

$v$

$G$

$G$

$v_{0},$ $v_{1},$$\cdots,v_{l}$In this section, we suppose that is a given fixed
positive integer greater than or equal to 3.
$k$

3.1

$k$

$k$

$k$

$G$

$G$

$G$

$G$

$U$

$C1^{c}$

$G$

.

$k$

Lemma 2 A graph $G=(V,E)$ is not -chordal if
and only if there is a subset of with size such
that
$k$

$U$

$V$

$k$

(1) $G[U]$ is a path $(v_{0},v_{1,k}\ldots, v-1)$ of length $k-1$
and the number of the edges in $G[U]$ is $k-1$ ,and(2)in graph G[V–\^U],is reachable tois defined by $N_{G}(U-\{v_{0}, v_{k-1}\})$
where$v_{k-1}$$v_{0}$$\hat{U}$$(v_{\pi(0)}, v_{\pi(1)}, \cdots,v_{\pi(1}\iota-),v)\pi(0)$$k$Recognition of a -Chordal Graph

The following lemma is crucial in this subsection:

$\pi$

$k$

-Chordal Graphs with Fixed$k$$U=\{v_{0}, v_{1}, \cdots,v_{\mathrm{I}}-1\}$

$l$

$k$

$G$

$d$

$d$

3

$\{v_{0},v_{k-1}\}$-.

Intuitively, when $U$ witnesses that is not k-chordal,$G[U]$ is just a path, not including extra edges, andthrough the vertices not in
is reachable tothe neighbors. of the intermediate vertices in the path
$G[U]$ (see Figure 1).
Proof. We first as sume that is not -chordal. Then
there is at least one minimal cycle $C$ of length at least$k+1$ . We let $U$ beconsecutive vertices on $C$ . Since$C$
has no chord, $G[U]$ is just a path, and contains
no vertex in $C-U$ . Moreover, the endpoints of thepath $G[U]$ are reachable to each other through thevertices $G[C-U]$ , or not through the vertices in .
Thus both conditions (1) and (2) hold for the $U$ .
Next we assume that we can take a set satisfying
both conditions (1) and (2). Let $P$ be the shortest
not through the vertices in .
path from
toThen, we have a cycle $C$ joining $P$ and $G[U]$ . Since
andis not adjacent to each other by (1), thelength of $C$ is at least $k+1$ . Thus, it is sufficient to$G$$v_{k-1}$$v_{0}$

$G$

$k$

$k$

$\hat{U}$$\hat{U}$$U$$\hat{U}$$v_{0}$

Proposition 1 For any graph $G,$
is -chordal if
if
each
only
] has size
andninimal vertex set in.
at most$G$$k$$C1^{c}$$k$$v_{0}$$v_{k-1}$$v_{k-1}$

29

Figure 1:$k$-chordalness of a graphshow that $C$ has no chord. By (1), $C$ has no chordwith two vertices both in $P$ . Since $P$ is the shortest
path, $C$ has no chord with two vertices both in $P$ .
Moreover, since $P$ andhave no common vertices,$C$ has no chord
between the vertices in $P$ and.
Thus is not k-chordal.
Now we are ready to show the NC recognition algorithm of a -chordal graph.
$\hat{U}$$G[U]\bullet$

For each set we check the reachability that requires$O(n+m)$ processors. Hence, we need at most a total
1of $O(n^{k+1}+n^{k}m)$ processors.
Now we turn to the recognition problem of a kchordal bipartite graph.

$G$

$k$

Algorithm RECOG
Input: A graph $G=(V, E)$ , and an integer$k$.

Output: “Yes” or “No”
1. For every set of size do in parallel;
1-1. If $G[U]$ is not a path return;
1-2. If two endpoints in the path $G[U]$ arereachable to each other in the graph
G[V–\^U], return “No”;
$U$

$k$

2. If there exists a set returning “No”, output“No”; else output “Yes”.
Theorem 3 Algorithm RECOG solves the recognition problem for -chordalness in $O(\log n)$ time using$O(n^{k+1}+n^{k}m)$ processors.

Lemma 4 A graph is not bipartite if and only if
contains at least one minimal cyclic vertex setof odd size.
$G$$C1^{c}]$

Proof. A graph $G$ is not bipartite if and only if it contains at least one odd length cycle (see e.g. [6]). We
assume that $G$ contains at least one odd length cycle.
A chord of any odd length cycle divides the cycle into
an odd length cycle and an even length cycle. Thus,$C[G]$ must contain at least one minimal cyclic vertex
1
set of odd size.

Theorem 5 A -chordal bipartite graph can be recognized in $O(\log n)$ time using $O(n^{k+1}+n^{k}m)$ pro$k$

cessors.

$k$

Proof. The correctness of the algorithm follows immediately from Lemma 2. Thus it is sufficient to show
the complexity of Algorithm RECOG.
In addition to the processors corresponding to thevertices and edges, we assign a processor to each set ofvertices of size . Thus, the step 1-1 can be performed
in a constant time. The step 1-2 can be carried out
using an algorithm that computes connected components. The parallel algorithm for this task runs in$O(\log n)$ time and uses $O(n+m)$ processors [20].
Next we count the number of processors. The number of the set of vertices of size is $=O(n^{k})$ .

In addition to the recognition for kProof.
chordalness, by Proposition 1 and Lemma 4, it is sufficient to check whether the graph contains at least
one minimal cyclic vertex set of odd size being lessthan or equal to . The check can be done by replacing the step 1-1 in Algorithm RECOG by the following
two steps:
$k$

$k$

$k$

1-1
1-1

. If $G[U1$ contains an odd length cycle return“No”;$(\mathrm{a})$$(\mathrm{b})$. If $G[U]$ is not a path return;This implies the theorem.

1

30

3.2

The MAS Problem on a k-Chordal
Graph

In this section, we consider the MAS problem on a-chordal graph. For any given graph $G=(V,E)$ , wea hypergraph (V, $C[G]$ ). That is, thedenote bycontains every minimal cyclic vertex
hypergraphset in as a hyperedge. We moreover let
be a setof vertices defined by { $v|v$ is not in any $U\in C[G]$ }.
That is, the set
contains every vertex not included in any cycle in . Then we have the following
lemma.
$k$$H_{G}$$H_{G}$$G$$W_{G}$$W_{G}$$G$

Lemma 6 For any graph and a subset of $V,$
is an MAS of if and only if
and $U-W_{G}$is an MIS of
.
$G$

$G$

a constant time. Thus, using the following facts, wehave the theorem: An MIS in a hypergraph of dimension 3 can be computed in $O(\log^{4}n)$ time using$n+m$ processors of an EREW PRAM, whereand$m$ are the number of vertices and edges, respectively[4]. The MIS problem on a hypergraph of dimension
I
is in RNC for any fixed positive integer $d[11]$ .
Remark: Chen proposed an NC algorithm for finding a maximal -cycle free set on a given chordal
graph [1]. Using his result, we can find an MAS ofa 3-chordal graph in $O(\log n)4$ time with $O(n+m)$
processors of an EREW PRAM [2].
$n$

$d$

$k$

$U$

$U$

$W_{G}\subseteq U$$H_{G}$-Chordal Graphs with General

4

$k$

$k$

1
Proof. For lack of space, we omit the proof.
Now we have the following algorithm for solving
the MAS problem.

Algorithm MAS

1. Find$W_{G}$$U$.

$H_{G}$, and add them into$U$-completeness of the Recognition for k-Chordalness$\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$k-$\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$.

The correctness of the algorithm follows immediatelyfrom Lemma 6. Now
uming that the graph is-chordal, and we have the main theorem in this section:$G$$\mathrm{a}ss$$n$Theorem 8 The recognition problem for
chordalness is-complete for $k=\Theta(n)$ .

and set $U:=W_{G;}V:=V-W_{G}$ .

2. Find an MIS of

$k$

$k$

4.1

Input: A graph $G=(V, E)$ .
Output: An MAS

We now turn to consider the -chordal graphs suchthat is a function of , the number of vertices.

$k$

Theorem 7 The MAS problem on a -chordal graphis in RNC for any fixed greater than 3. An MAS ofa 3-chordal graph can be computed in $O(\log^{4}n)$ timewith $O(n^{3})$ processors of an EREW PRAM.
$k$

$k$

Proof. We assume that the given graph is k-chordal.
We show that Algorithm MAS can be implemented
in NC except finding an MIS. In addition to the processors corresponding to vertices and edges in , weassign each vertex set of size at most . The as signment requires $\sum_{i=3}^{k}=O(n^{k})$ processors. The
step 1 can be done by the following steps:
$G$

$k$

1-1. In parallel, each processor corresponding to avertex set of size at most marks its all elements if it is cyclic.

Proof. Hamiltonian cycle problem is NP-complete
even on a 3-regular graph [9]. We show a polynomial
time reduction from the problem to the complementof the recognition problem. Let $G=(V, E)$ be a given

3-regular graph. Let $G’=(V’, E’)$ be the graph obtained from by the following replacements:$G$(1) For each edge in $E$ , replace it by a path oflength 2 (see Figure $2(1)$ ).
(2) For each vertex in $V$, replace it by the gadget
given in Figure 2(2).
Let $|V|=n$ , then $|E|= \frac{3}{2}n$ since $G$ is 3-regular.
For the resulting graph $G’$ , it is not difficult to
see that $|V’|=n(n+5)+ \frac{3}{2}n=n^{2}+\frac{13}{2}n$ and$|E’|=n(n+7)+2 \frac{3}{2}n=n^{2}+10n$ . This reduction
can be done in polynomial time.
We now consider the complement of the recognition
problem for -chordalness on $G’$ as follows:
$k$

$k$

1-2. Set all unmarked vertices into

$W_{G}$.

$G^{J}$

and $k=n^{2}+n-1$ .

Question: Is $G’$ not k-chordal?

The steps can be done in a constant time since is aconstant. Moreover, through the steps, each processor can know whether the vertex set is minimal cyclic
set. By Proposition 1, every minimal cyclic set can befound by the steps. This implies that the algorithm
can construct the hypergraphafter the step 1 in$k$

$H_{G}$

Input:

It is sufficient to show that has a Hamiltonian cycle
if and only if $G’$ is not -chordal. We first remark thateach edge in $G’$ has at least one endpoint of degree
2, and it can not be a chord. That is, the resulting
graph $G’$ has no chord. Thus, $G’$ is not -chordal if
and only if $G’$ has a cycle of length greater than .
$G$

$k$

$k$

$k$

31

$\mathrm{D}$(2)$\mathrm{D}$Figure 2: Replacements

We first as sume that has a Hamiltonian cycle, or
has a simple cycle of length . Then, we can tracegadgets following the order of the vertices on the
Hamiltonian cycle, and in each gadget we can have asimple path of vertices (including the entrance andexit vertices). Thus, counting the number of vertices
on the trace, we have a cycle of length $n^{2}+n=k+1$
in $G’$ , consequently, $G’$ is not k-chordal.
We next assume that $G’$ has a simple cycle of length
at least $k+1=n^{2}+n$ . Since each gadget has threepoints to enter and exit, the simple cycle can visit
each gadget at most once. Thus each gadget cancontribute at most vertices to the cycle. To derivea contradiction, we moreover assume that the cycle
visits at most $n-1$ gadgets. The number of the edges, which is equal to the number of the verin is
tices not included in the gadgets in $G’$ . Thus thenumber of the vertices on the cycle is bounded above
by $\frac{3}{2}n+(n-1)n=n^{2}+\frac{1}{2}n<n^{2}+n$ , which contradicts. Therefore, the cycle visits every gadget once.
Thus the order of the gadgets on the cycle gives aI
Hamiltonian cycle in .
$G$

$G$

$n$

$n$

$n$

$n$

$G$

$\frac{3}{2}n$

$G$

4.2

Lower Bound of NP-completenessFor any-complete problem on a general graph,
we give a lower bound of such that it is also NPcomplete on a -chordal graph by a padding argument:$\mathrm{N}\mathrm{P}$

$k$

$k$

Theorem 9 Every-complete problem on an nchordal graph is also
-complete on a-chordal$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$$cn^{\epsilon}$graph for any fixed positive constants

$c$

and

$\epsilon$.

Proof. We reduce the problem on an n-chordal
graph to the problem on a-chordal graph. For
a given graph $G=(V, E)$ with vertices, we construct a new graph $G^{l}=(V’,E;)$ that consists ofcopies of as follows: Fix any$V$$f(n)$
vertex in , joint
copies of using a path oflength $f(n)-1$ through every copy of .
Clearly, this is a polynomial time reduction. Moreover,is an -chordal graph with $n’=nf(n)$ ver,tices. Since1
this completes the proof.
Combining Theorem 8 and the padding in the proofof Theorem 9, we also have the following corollary:$cn^{\epsilon}$

$n$

$G$

$f(n)= \lceil(\frac{1}{c})^{\frac{1}{\epsilon}1}n^{\frac{1}{\epsilon}-}\rceil$

$G$

$v$

$v$

$G^{l}$$n$$n=c(( \frac{1}{c})^{\frac{1}{\epsilon}}n\frac{1}{\epsilon})^{\epsilon}\leq c(nf(n))^{\epsilon}=cn^{\prime\epsilon}$

Corollary 10 For any fixed positive constant
the recognition problem for -chordalness iscomplete even for.
$k$$\epsilon$,$\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{p}_{-}$$k=\Theta(n^{\epsilon})$5

Concluding Remarks

Recently, parameterized problems are widely investigated [7], and the recognizing -chordalness can be
regarded as a kind of such problems. From the pointof view, it is further work to determine if the recognition problem-for -chordalness is fixed-parametertractable.
We can regard Lemma 2 as a nontrivial generalization of [8, Lemma 23] in the sense that we can obtain the same claim from Lemma 2 by setting $k=3$ .
$k$

$k$

32

[7] R.G. Downey and M.R. Fellows. Parameterized

These lemmas use the property of a -chordal graphstraightforwardly. On the other hand, Naor, Naor,and Sch\"affer [17], and Klein [12] use two nontrivial
characterizations of a 3-chordal graph; one is the intersection graph characterization, and the other isthe perfect elimination ordering. From both algorithmical and graph theoretical points of view, it isworth finding such nontrivial characterizations of a-chordal graph.
Some results for 4-chordal bipartite graphs immedi-completeness of finding the following
ately statesets on a 4-chordal graph: Steiner tree and dominating set [16], variants of dominating set [5], andHamiltonian cycle [15]. On the other hand, as men-complete problems
tioned in Introduction, several
on a general graph are polynomial time solvable ona 3-chordal graph. The following are natural ques-complete problems on a 4tions: whether thechordal graph are polynomial time solvable on a 3chordal graph; and whether the polynomial time solvable problems on a 3-chordal graph are NP-complete
on a 4-chordal graph.

[10] F. Gavril. Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by
Cliques, and Maximum Independent Set of a
Chordal Graph. SIAM J. on Comp., $1(2):180^{-}$
187, 1972.

Acknowledgment[13] J. van Leeuwen. Handbook of Theoretical Computer Science. Elsevier Science Publishers, 1990.

$k$Complexity. Springer, 1999.

[8] A. Edenbrandt. Chordal Graph Recognition isin NC. IPL, 24:239-241, 1987.
[9] M.R. Garey and D.S. Johnson. Computers andIntractability –A Guide to the Theory of NPCompleteness. Freeman, 1979.

$k$$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$I thank Professor Zhi-Zhong Chen, who read my earlier draft, sent me his unpublished document, noticed
the efficient algorithm for the MAS problem on a 3chordal graph, and gave me some fruitful suggestions.
My thanks also to Professor Koichi Yamazaki for discussions and encouragement.

[11] P. Kelsen. On the Parallel Complexity of Computing a Maximal Independent Set in a Hypergraph. In Proc. 24th STOC, pages 339-350.
ACM, 1992.
[12] P.N. Klein. Efficient Parallel Algorithms for
Chordal Graphs. SIAM J. on Comp., $25(4):797-$

827, 1996.

[14] A. Lubiw. Doubly Lexical Orderings of Matrices.
SIAM J. on Comp., $16(5):854-879$ , 1987.
[15] H. M\"uuer. Hamiltonian Circuit in Chordal Bipartite Graphs. Disc. Math., 156:291-298, 1996.

References

The NP[16] H. M\"uller and A. Brandst\"adt.
Completeness of Steiner Tree and Dominating
Set for Chordal Bipartite Graphs. TCS, 53:257265, 1987.

[1] Z.-Z. Chen. NC Algorithms for Finding Maximal -Cycle Free Sets in Simple Graphs.
manuscript, 1993.

[17] J. Naor, M. Naor, and A.A. Sch\"affer. Fast Parallel Algorithms for Chordal Graphs. SIAM J.
on Comp., $18(2):327-349$ , 1989.

[2] Z.-Z. Chen. Personal communication. 1998.

[18] R. Paige and R.E. Tarjan. Three Partition
Refinement Algorithms. SIAM J. on Comp.,$k$[3] Z.-Z. Chen and X. He. Parallel Algorithms for
Maximal Acyclic Sets. Algorithmica, 19:354-368,

1997.

[4] E. Dahlhaus, M. Karpinski, and P. Kelsen. An
efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3. IPL, 42:309-313, 1992.
[5] P. Damaschke, E. M\"uller, and D. Kratsch.
Domination in Convex and Chordal Bipartite
Graphs. IPL, 36:231-236, 1990.
[6] R. Diestel. Graph Theory. Springer, 1996.

$16(6):973-989$ , 1987.

[19] D. Pearson and V.V. Vazirani. Efficient Sequential and Parallel Algorithms for Maximal Bipar, 14:171-179, 1993.
tite Sets. J. of Algo$\mathit{7}\dot{\mathrm{r}}thmS$[20] Y. Shiloach and U. Vishkin. An $O(\log n)$ parallel connectivity algorithm. J. of Algorithms,

3:57-67, 1982.

[21] R. Uehara and Z.-Z. Chen. Parallel Algorithms
for Maximal Linear Forests. The Trans. of the
IEICE, E80-A(4) $:627^{-634}$ , 1997.