{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:27Z","timestamp":1740133947954,"version":"3.37.3"},"reference-count":16,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"name":"DST SERB","award":["CRG\/2020\/005964"],"award-info":[{"award-number":["CRG\/2020\/005964"]}]},{"name":"DST SERB","award":["CRG\/2020\/005964"],"award-info":[{"award-number":["CRG\/2020\/005964"]}]},{"DOI":"10.13039\/100020368","name":"Nanotechnology Innovation Centre","doi-asserted-by":"publisher","award":["CRG\/2020\/005964"],"award-info":[{"award-number":["CRG\/2020\/005964"]}],"id":[{"id":"10.13039\/100020368","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p> 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 [Formula: see text] rounds and [Formula: see text] messages, where [Formula: see text] is the size of the maximum independent set and [Formula: see text] is the number of nodes in the graph. We provide a matching lower bound of [Formula: see text] on the number of rounds, whereas [Formula: see text] 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 [Formula: see text] graphs, a special case of the interval graphs where the intervals have exactly [Formula: see text] different lengths. We propose an [Formula: see text]-approximation algorithm that runs in [Formula: see text] round. For axis-parallel segment intersection graphs, we design an [Formula: see text]-approximation algorithm that obtains a solution in [Formula: see text] rounds. The results in this paper extend the results of Molla et al. [J. Parallel Distrib. Comput. 2019]. <\/jats:p>","DOI":"10.1142\/s0129054124500084","type":"journal-article","created":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T08:50:56Z","timestamp":1720601456000},"page":"67-95","source":"Crossref","is-referenced-by-count":0,"title":["Distributed Independent Sets in Interval and Segment Intersection Graphs"],"prefix":"10.1142","volume":"36","author":[{"given":"Nirmala","family":"Bhatt","sequence":"first","affiliation":[{"name":"Mehta Family School of Data Science and Artificial Intelligence, Indian Institute of Technology Roorkee, Roorkee, Uttarakhand, India"}]},{"given":"Barun","family":"Gorain","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Bhilai, Raipur, Chattisgarh, India"}]},{"given":"Kaushik","family":"Mondal","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Ropar, Rupnagar, Punjab, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4908-7165","authenticated-orcid":false,"given":"Supantha","family":"Pandit","sequence":"additional","affiliation":[{"name":"Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar, Gujarat, India"}]}],"member":"219","published-online":{"date-parts":[[2024,7,9]]},"reference":[{"key":"S0129054124500084BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"S0129054124500084BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"S0129054124500084BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933068"},{"key":"S0129054124500084BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"S0129054124500084BIB005","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.140"},{"key":"S0129054124500084BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"S0129054124500084BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48653-5_37"},{"key":"S0129054124500084BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_21"},{"key":"S0129054124500084BIB009","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"S0129054124500084BIB010","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"S0129054124500084BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22146"},{"key":"S0129054124500084BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2019.05.012"},{"key":"S0129054124500084BIB013","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"S0129054124500084BIB014","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"S0129054124500084BIB015","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"S0129054124500084BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0097-1"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054124500084","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T07:18:50Z","timestamp":1738653530000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054124500084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,9]]},"references-count":16,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.1142\/S0129054124500084"],"URL":"https:\/\/doi.org\/10.1142\/s0129054124500084","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2024,7,9]]}}}