An optimal parallel algorithm for the minimum circle-cover problem

DOI10.1016/0020-0190(89)90037-9zbMath0677.68033OpenAlexW2019251879MaRDI QIDQ1123605

Mikhail J. Atallah, Danny Z. Chen

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1691&context=cstech

zbMATH Keywords

combinatorial problemsanalysis of algorithmsparallel processingcomputational geometrycircle-cover problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Related Items

Capacitated Arc Stabbing ⋮ An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications ⋮ OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS ⋮ Algorithms for interval structures with applications ⋮ Testing a simple polygon for monotonicity optimally in parallel ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Parallel algorithms on circular-arc graphs ⋮ Optimal parallel algorithm for shortest-paths problem on interval graphs

Cites Work

• On a circle-cover minimization problem
• Parallel circle-cover algorithms
• An Efficient Parallel Biconnectivity Algorithm
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Parallel Merge Sort
• Parallel Prefix Computation