Distributed independent sets in interval and segment intersection graphs

DOI10.1007/978-3-030-67731-2_13zbMath1490.68155OpenAlexW3123958729MaRDI QIDQ831804

Kaushik Mondal, Supantha Pandit, Barun Gorain

Publication date: 24 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-67731-2_13

zbMATH Keywords

approximation algorithminterval graphdistributed algorithmmaximal independent setsegment intersection graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62) Distributed algorithms (68W15)

Related Items (1)

Distributed dominating sets in interval graphs

Cites Work

• Unnamed Item
• An optimal maximal independent set algorithm for bounded-independence graphs
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Distributed large independent sets in one round on bounded-independence graphs
• Local Computation
• Fast Distributed Approximations in Planar Graphs
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• On the Complexity of Distributed Network Decomposition
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Brief Announcement
• Distributed Computing
• Deterministic Distributed Vertex Coloring in Polylogarithmic Time

This page was built for publication: Distributed independent sets in interval and segment intersection graphs