Distributed independent sets in interval and segment intersection graphs

DOI10.1007/978-3-030-67731-2_13zbMATH Open1490.68155OpenAlexW3123958729MaRDI QIDQ831804FDOQ831804

Authors: Barun Gorain, Kaushik Mondal, Supantha Pandit 

Publication date: 24 March 2022

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

Recommendations

• An optimal maximal independent set algorithm for bounded-independence graphs
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• An Improved Distributed Algorithm for Maximal Independent Set
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• MIS on trees

zbMATH Keywords

approximation algorithmdistributed algorithmmaximal independent setinterval graphsegment intersection graph

Mathematics Subject Classification ID

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

Cites Work

• Distributed Computing: A Locality-Sensitive Approach
• Locality in Distributed Graph Algorithms
• Distributed Computing
• Local computation: lower and upper bounds
• Fast Distributed Approximations in Planar Graphs
• On the Complexity of Distributed Network Decomposition
• Deterministic distributed vertex coloring in polylogarithmic time
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• An optimal maximal independent set algorithm for bounded-independence graphs
• Distributed large independent sets in one round on bounded-independence graphs
• An Improved Distributed Algorithm for Maximal Independent Set
• Tight analysis of parallel randomized greedy MIS
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Brief Announcement

Cited In (2)

• Reconfiguring Independent Sets on Interval Graphs
• Distributed dominating sets in interval graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831804)