Parallel circle-cover algorithms
Given a set of n circular-arcs, each possibly having a real weight, we consider the problem of finding a subset of the arcs whose union covers the whole circle. We provide parallel algorithms running in O(log n) and \(O(\log^ 2 n)\) time, respectively, for finding a circle-cover with the smallest number of arcs and with the smallest overall weight. The algorithms require, respectively, \(O(n^ 2/\log n+qn)\) and \(O(n^ 3/\log n)\) processors on a shared memory model (SMM) of parallel computers, where q-1 is the minimum number of arcs crossing any point of the circle.
- An improved parallel algorithm for maximal matching
- An introduction to parallelism in combinatorial optimization
- Binary Trees and Parallel Scheduling Algorithms
- Bounds to Complexities of Networks for Sorting and for Switching
- scientific article; zbMATH DE number 3905859 (Why is no real title available?)
- On a circle-cover minimization problem
- Parallel Matrix and Graph Algorithms
- Some parallel algorithms on interval graphs
- An optimal parallel algorithm for the minimum circle-cover problem
- Placing segments on parallel arcs
- A parallel circle-cover minimization algorithm
- An optimal parallel circle-cover algorithm
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- Capacitated Arc Stabbing
- Optimal parallel algorithm for shortest-paths problem on interval graphs
- Algorithms for interval structures with applications
- On a circle-cover minimization problem
This page was built for publication: Parallel circle-cover algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108792)
