Parallel complexity of partitioning a planar graph into vertex-induced forests

Zhi Zhong Chen; Xin He

doi:10.1016/0166-218x(96)00089-3

Parallel complexity of partitioning a planar graph into vertex-induced forests

Zhi Zhong Chen
, Xin He

Department of Computer Science and Engineering

Tokyo Denki University

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

We present the first NC algorithm for partitioning the vertex set of a given planar graph into three subsets, each of which induces a forest. The algorithm runs in O(log n log* n) time using O(n/(log n log* n)) processors on an EREW PRAM. We also present optimal NC algorithms for partitioning the vertex set of a given K₄-free or K_2,3-free graph (special planar graph) into two subsets, each of which induces a forest.

Original language	English
Pages (from-to)	183-198
Number of pages	16
Journal	Discrete Applied Mathematics
Volume	69
Issue number	1-2
DOIs	https://doi.org/10.1016/0166-218x(96)00089-3
State	Published - Aug 13 1996

Access to Document

10.1016/0166-218x(96)00089-3

Cite this

@article{89e04121b2804a778a8ea1186cc022f1,

title = "Parallel complexity of partitioning a planar graph into vertex-induced forests",

abstract = "We present the first NC algorithm for partitioning the vertex set of a given planar graph into three subsets, each of which induces a forest. The algorithm runs in O(log n log* n) time using O(n/(log n log* n)) processors on an EREW PRAM. We also present optimal NC algorithms for partitioning the vertex set of a given K4-free or K2,3-free graph (special planar graph) into two subsets, each of which induces a forest.",

author = "Chen, \{Zhi Zhong\} and Xin He",

year = "1996",

month = aug,

day = "13",

doi = "10.1016/0166-218x(96)00089-3",

language = "English",

volume = "69",

pages = "183--198",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Parallel complexity of partitioning a planar graph into vertex-induced forests

AU - Chen, Zhi Zhong

AU - He, Xin

PY - 1996/8/13

Y1 - 1996/8/13

N2 - We present the first NC algorithm for partitioning the vertex set of a given planar graph into three subsets, each of which induces a forest. The algorithm runs in O(log n log* n) time using O(n/(log n log* n)) processors on an EREW PRAM. We also present optimal NC algorithms for partitioning the vertex set of a given K4-free or K2,3-free graph (special planar graph) into two subsets, each of which induces a forest.

AB - We present the first NC algorithm for partitioning the vertex set of a given planar graph into three subsets, each of which induces a forest. The algorithm runs in O(log n log* n) time using O(n/(log n log* n)) processors on an EREW PRAM. We also present optimal NC algorithms for partitioning the vertex set of a given K4-free or K2,3-free graph (special planar graph) into two subsets, each of which induces a forest.

UR - https://www.scopus.com/pages/publications/0042541350

U2 - 10.1016/0166-218x(96)00089-3

DO - 10.1016/0166-218x(96)00089-3

M3 - Article

AN - SCOPUS:0042541350

SN - 0166-218X

VL - 69

SP - 183

EP - 198

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-2

ER -

Parallel complexity of partitioning a planar graph into vertex-induced forests

Abstract

Access to Document

Other files and links

Fingerprint

Cite this