A parrallel algorithm for partitioning a point set to minimize the maximum of diameters

被引：0
|
作者：
Alsuwaiyel, MH [1 ]
机构：
[1] King Fahd Univ Petr & Minerals, Dept Informat & Comp Sci, Dhahran 31261, Saudi Arabia
来源：
INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-IV, PROCEEDINGS | 1998年
关键词：
computational geometry; simple polygon; diameter; maximum of diameters; parallel algorithms;
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Given a set S of n points ist the plane, we consider the problem of partitioning S into two subsets such that the masimum of their diameters is minimized. We present a parallel algorithm to solve this problem that runs in time O(log n log log n) using the GREW PRAM model of computation with O(n(2)) processors.
引用
收藏
页码：698 / 701
页数：4
相关论文
共 50 条
  • [41] A spectral partitioning algorithm for maximum directed cut problem
    Zhang, Zhenning
    Du, Donglei
    Wu, Chenchen
    Xu, Dachuan
    Zhang, Dongmei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2021, 42 (03) : 373 - 395
  • [42] A genetic algorithm for maximum independent set problems
    Liu, XZ
    Sakamoto, A
    Shimamoto, T
    INFORMATION INTELLIGENCE AND SYSTEMS, VOLS 1-4, 1996, : 1916 - 1921
  • [43] Maximum Independent Set Algorithm for Hypergraph Data
    Xu L.-T.
    Li R.-H.
    Dai Y.-H.
    Wang G.-R.
    Ruan Jian Xue Bao/Journal of Software, 2024, 35 (06): : 2999 - 3012
  • [44] HEURISTIC ALGORITHM FOR FINDING THE MAXIMUM INDEPENDENT SET
    Plotnikov, A. D.
    CYBERNETICS AND SYSTEMS ANALYSIS, 2012, 48 (05) : 673 - 680
  • [45] EXTENDING THE MAX ALGORITHM FOR MAXIMUM INDEPENDENT SET
    Le, Ngoc C.
    Brause, Christoph
    Schiermeyer, Ingo
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2015, 35 (02) : 365 - 386
  • [46] A novel algorithm for solution of a combinatory set partitioning problem
    Lyubetsky, V. A.
    Seliverstov, A. V.
    JOURNAL OF COMMUNICATIONS TECHNOLOGY AND ELECTRONICS, 2016, 61 (06) : 705 - 708
  • [47] Genetic algorithm for distance balancing in set partitioning problems
    Kiremitci, Serap
    Akyurt, Ibrahim Zeki
    ISTANBUL UNIVERSITY JOURNAL OF THE SCHOOL OF BUSINESS, 2012, 41 (01): : 47 - 61
  • [48] A Relax-and-Cut algorithm for the set partitioning problem
    Cavalcante, Victor F.
    de Souza, Cid C.
    Lucena, Abilio
    COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (06) : 1963 - 1981
  • [49] Network relaxation based enumeration algorithm for set partitioning
    Ali, Agha Iqbal, 1600, (38):
  • [50] A novel algorithm for solution of a combinatory set partitioning problem
    V. A. Lyubetsky
    A. V. Seliverstov
    Journal of Communications Technology and Electronics, 2016, 61 : 705 - 708
12345