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

被引：11
|
作者：
Chen, ZZ [1 ]
He, X [1 ]
机构：
[1] SUNY BUFFALO,DEPT COMP SCI,BUFFALO,NY 14260
来源：
DISCRETE APPLIED MATHEMATICS | 1996年 / 69卷 / 1-2期
关键词：
D O I：
10.1016/0166-218X(96)00089-3
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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-4-free or K-2,K-3-free graph (special planar graph) into two subsets, each of which induces a forest.
引用
收藏
页码：183 / 198
页数：16
相关论文
共 50 条
  • [31] Partitioning planar graphs into bounded degree forests
    Wang, Yang
    Wang, Jiali
    Wang, Weifan
    Kong, Jiangxu
    APPLIED MATHEMATICS AND COMPUTATION, 2024, 474
  • [32] Partitioning a bipartite graph into vertex-disjoint paths
    Li, Jianping
    Steiner, George
    ARS COMBINATORIA, 2006, 81 : 161 - 173
  • [33] On the vertex partition of planar graphs into forests with bounded degree
    Wang, Yang
    Huang, Danjun
    Finbow, Stephen
    APPLIED MATHEMATICS AND COMPUTATION, 2020, 374
  • [34] Parallel Planar Subgraph Isomorphism and Vertex Connectivity
    Gianinazzi, Lukas
    Hoefler, Torsten
    PROCEEDINGS OF THE 32ND ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA '20), 2020, : 269 - 280
  • [35] Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube
    Jha, Pranava K.
    DISCRETE APPLIED MATHEMATICS, 2023, 337 : 218 - 231
  • [36] PARALLEL TASK ASSIGNMENT BY GRAPH PARTITIONING
    LIU, SF
    SOFFA, ML
    LECTURE NOTES IN COMPUTER SCIENCE, 1992, 605 : 965 - 966
  • [37] Graph partitioning models for parallel computing
    Hendrickson, B
    Kolda, TG
    PARALLEL COMPUTING, 2000, 26 (12) : 1519 - 1534
  • [38] A parallel multilevel metaheuristic for graph partitioning
    Baños, R
    Gil, C
    Ortega, J
    Montoya, FG
    JOURNAL OF HEURISTICS, 2004, 10 (03) : 315 - 336
  • [39] A Parallel Multilevel Metaheuristic for Graph Partitioning
    R. Baños
    C. Gil
    J. Ortega
    F.G. Montoya
    Journal of Heuristics, 2004, 10 : 315 - 336
  • [40] Current challenges in parallel graph partitioning
    Pellegrini, Francois
    COMPTES RENDUS MECANIQUE, 2011, 339 (2-3): : 90 - 95
12345