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
approximation algorithminterval graphdistributed algorithmmaximal independent setsegment intersection graph
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)
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
