Parallel Algorithms for the Maximal Tree Cover Problems

Zhi-Zhong CHEN; Takumi KASAI

Parallel Algorithms for the Maximal Tree Cover Problems

Zhi-Zhong CHEN, Takumi KASAI

Full Text Views

0

Cite this

Summary :

A maximal l-diameter tree cover of a graph G(V,E) is a spanning subgraph C(V,E_C) of G such that each connected component of C is a tree, C contains no path with more than l edges, and adding any edge in EE_C to C yields either a path of length l1 or a cycle. For every function f from positive integers to positive integers, the maximal f-diameter tree cover prolem (MDTC(f) problem for short) is to find a maximal f(n)-diameter tree cover of G, given an n-node graph G. In this paper, we give two parallel algorithms for the MDTC(f) problem. The first algorithm can be implemented in time O(T_MSP(n,f(n))log²n) using polynomial number of processors on an EREW PRAM, where T_MSP(n,f(n) is the time needed to find a maximal set of vertex disjoint paths of length f(n) in a given n-node graph using polynomial number of processors on an EREW PRAM. We then show that if suitable restrictions are imposed on the input graph and/or on the magnitude of f, then T_MSP(n,f(n))O(log^kn) for some constant k and thus, for such cases, we obtain an NC algorithm for the MDTC(f) problem. The second algorithm runs in time O(n log²n/{f(n)1}) using polynomial number of processors on an EREW PRAM. Thus if f(n)Ω(n/log^kn) for some kO, we obtain an NC algorithm for the MDTC(f) problem.

Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.1 pp.30-34

Publication Date: 1992/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)

Category

Cite this

Copy

Zhi-Zhong CHEN, Takumi KASAI, "Parallel Algorithms for the Maximal Tree Cover Problems" in IEICE TRANSACTIONS on Information, vol. E75-D, no. 1, pp. 30-34, January 1992, doi: .
Abstract: A maximal l-diameter tree cover of a graph G(V,E) is a spanning subgraph C(V,E_C) of G such that each connected component of C is a tree, C contains no path with more than l edges, and adding any edge in EE_C to C yields either a path of length l1 or a cycle. For every function f from positive integers to positive integers, the maximal f-diameter tree cover prolem (MDTC(f) problem for short) is to find a maximal f(n)-diameter tree cover of G, given an n-node graph G. In this paper, we give two parallel algorithms for the MDTC(f) problem. The first algorithm can be implemented in time O(T_MSP(n,f(n))log²n) using polynomial number of processors on an EREW PRAM, where T_MSP(n,f(n) is the time needed to find a maximal set of vertex disjoint paths of length f(n) in a given n-node graph using polynomial number of processors on an EREW PRAM. We then show that if suitable restrictions are imposed on the input graph and/or on the magnitude of f, then T_MSP(n,f(n))O(log^kn) for some constant k and thus, for such cases, we obtain an NC algorithm for the MDTC(f) problem. The second algorithm runs in time O(n log²n/{f(n)1}) using polynomial number of processors on an EREW PRAM. Thus if f(n)Ω(n/log^kn) for some kO, we obtain an NC algorithm for the MDTC(f) problem.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_1_30/_p

Copy

@ARTICLE{e75-d_1_30,
author={Zhi-Zhong CHEN, Takumi KASAI, },
journal={IEICE TRANSACTIONS on Information},
title={Parallel Algorithms for the Maximal Tree Cover Problems},
year={1992},
volume={E75-D},
number={1},
pages={30-34},
abstract={A maximal l-diameter tree cover of a graph G(V,E) is a spanning subgraph C(V,E_C) of G such that each connected component of C is a tree, C contains no path with more than l edges, and adding any edge in EE_C to C yields either a path of length l1 or a cycle. For every function f from positive integers to positive integers, the maximal f-diameter tree cover prolem (MDTC(f) problem for short) is to find a maximal f(n)-diameter tree cover of G, given an n-node graph G. In this paper, we give two parallel algorithms for the MDTC(f) problem. The first algorithm can be implemented in time O(T_MSP(n,f(n))log²n) using polynomial number of processors on an EREW PRAM, where T_MSP(n,f(n) is the time needed to find a maximal set of vertex disjoint paths of length f(n) in a given n-node graph using polynomial number of processors on an EREW PRAM. We then show that if suitable restrictions are imposed on the input graph and/or on the magnitude of f, then T_MSP(n,f(n))O(log^kn) for some constant k and thus, for such cases, we obtain an NC algorithm for the MDTC(f) problem. The second algorithm runs in time O(n log²n/{f(n)1}) using polynomial number of processors on an EREW PRAM. Thus if f(n)Ω(n/log^kn) for some kO, we obtain an NC algorithm for the MDTC(f) problem.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Parallel Algorithms for the Maximal Tree Cover Problems
T2 - IEICE TRANSACTIONS on Information
SP - 30
EP - 34
AU - Zhi-Zhong CHEN
AU - Takumi KASAI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1992
AB - A maximal l-diameter tree cover of a graph G(V,E) is a spanning subgraph C(V,E_C) of G such that each connected component of C is a tree, C contains no path with more than l edges, and adding any edge in EE_C to C yields either a path of length l1 or a cycle. For every function f from positive integers to positive integers, the maximal f-diameter tree cover prolem (MDTC(f) problem for short) is to find a maximal f(n)-diameter tree cover of G, given an n-node graph G. In this paper, we give two parallel algorithms for the MDTC(f) problem. The first algorithm can be implemented in time O(T_MSP(n,f(n))log²n) using polynomial number of processors on an EREW PRAM, where T_MSP(n,f(n) is the time needed to find a maximal set of vertex disjoint paths of length f(n) in a given n-node graph using polynomial number of processors on an EREW PRAM. We then show that if suitable restrictions are imposed on the input graph and/or on the magnitude of f, then T_MSP(n,f(n))O(log^kn) for some constant k and thus, for such cases, we obtain an NC algorithm for the MDTC(f) problem. The second algorithm runs in time O(n log²n/{f(n)1}) using polynomial number of processors on an EREW PRAM. Thus if f(n)Ω(n/log^kn) for some kO, we obtain an NC algorithm for the MDTC(f) problem.
ER -