*Result*: Distributed Independent Sets in Interval and Segment Intersection Graphs.
*Further Information*
*The Maximum Independent Set problem is well-studied in graph theory and related areas. An independent set of a graph is a subset of non-adjacent vertices of the graph. A maximum independent set is an independent set of maximum size. This paper studies the Maximum Independent Set problem in some classes of geometric intersection graphs in a distributed setting. More precisely, we study the Maximum Independent Set problem on two geometric intersection graphs, interval and axis-parallel segment intersection graphs, and present deterministic distributed algorithms in a model that is similar but a little weaker than the local communication model. We compute the maximum independent set on interval graphs in O (k) rounds and O (n) messages, where k is the size of the maximum independent set and n is the number of nodes in the graph. We provide a matching lower bound of Ω (k) on the number of rounds, whereas Ω (n) is a trivial lower bound on message complexity. Thus, our algorithm is both time and message-optimal. We also study the Maximum Independent Set problem in interval count l graphs, a special case of the interval graphs where the intervals have exactly l different lengths. We propose an 1 2 -approximation algorithm that runs in O (l) round. For axis-parallel segment intersection graphs, we design an 1 2 -approximation algorithm that obtains a solution in O (D) rounds. The results in this paper extend the results of Molla et al. [J. Parallel Distrib. Comput. 2019]. [ABSTRACT FROM AUTHOR]*