TY - GEN
T1 - NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems
AU - Chen, Zhi Zhong
AU - He, Xin
N1 - Publisher Copyright:
© 1995, Springer-Verlag Berlin Heidelberg 1995.
PY - 1995
Y1 - 1995
N2 - It is well known that the vertex set of every planar graph can be partitioned into three subsets each of which induces a forest. Previously, there has been no NC algorithm for computing such a partition. In this paper, we design an optimal NC algorithm for computing such a partition for a given planar graph. It runs in O(log n log* n) time using O(n/(log n log* n)) processors on an EREW PRAM. This algorithm implies optimal NC approximation algorithms for many NP-hard maximum induced subgraph problems on planar graphs with a performance ratio of 3. We also present optimal NC algorithms for partitioning the vertex set of a given K4-free or K2,3-free graph into two subsets each of which induces a forest. As consequences, we obtain optimal NC algorithms for 4-coloring K4-free or K2,3-free graphs which are previously unknown to our knowledge.
AB - It is well known that the vertex set of every planar graph can be partitioned into three subsets each of which induces a forest. Previously, there has been no NC algorithm for computing such a partition. In this paper, we design an optimal NC algorithm for computing such a partition for a given planar graph. It runs in O(log n log* n) time using O(n/(log n log* n)) processors on an EREW PRAM. This algorithm implies optimal NC approximation algorithms for many NP-hard maximum induced subgraph problems on planar graphs with a performance ratio of 3. We also present optimal NC algorithms for partitioning the vertex set of a given K4-free or K2,3-free graph into two subsets each of which induces a forest. As consequences, we obtain optimal NC algorithms for 4-coloring K4-free or K2,3-free graphs which are previously unknown to our knowledge.
UR - https://www.scopus.com/pages/publications/21844483819
U2 - 10.1007/3-540-60618-1_82
DO - 10.1007/3-540-60618-1_82
M3 - Conference contribution
AN - SCOPUS:21844483819
SN - 3540606181
SN - 9783540606185
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 275
EP - 289
BT - Graph-Theoretic Concepts in Computer Science - 21st International Workshop, WG 1995, Proceedings
A2 - Nagl, Manfred
PB - Springer Verlag
T2 - 21st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1995
Y2 - 20 June 1995 through 22 June 1995
ER -