Search

Your search keyword '"Pandit, Supantha"' showing total 67 results
Start Over Author "Pandit, Supantha"
67 results on '"Pandit, Supantha"'

56. Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line

Author

Mudgal, Apurva, Pandit, Supantha, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Lu, Zaixin, editor, Kim, Donghyun, editor, Wu, Weili, editor, Li, Wei, editor, and Du, Ding-Zhu, editor

Published
2015
Full Text
View/download PDF

58. Generalized Class Cover Problem with Axis-Parallel Strips

Author

Mudgal, Apurva, Pandit, Supantha, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Pal, Sudebkumar Prasant, editor, and Sadakane, Kunihiko, editor

Published
2014
Full Text
View/download PDF

67. Distributed Independent Sets in Interval and Segment Intersection Graphs.

Author

Bhatt, Nirmala, Gorain, Barun, Mondal, Kaushik, and Pandit, Supantha

Subjects
*INDEPENDENT sets, *INTERSECTION graph theory, *GRAPH theory, *DETERMINISTIC algorithms, *DISTRIBUTED algorithms, *LOCAL mass media, *COMMUNICATION models
Abstract

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]

Published
2024
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results