9 citations · 17 across the 12 of their papers we have counts for
18 papers
Witness Set: A Visibility Problem in
Satyabrata Jana, Debabrata Pal, Bodhayan Roy +1
We study the Witness Set problem, a natural dual to the classical Art Gallery problem. In the Witness Set problem, we are given a polygon and an integer as input, and the o…
Some results on Minimum Consistent Subsets of Trees
Bubai Manna, Bodhayan Roy
For a graph G = (V,E) where each vertex is coloured by one of k colours, consider a subset C of V such that for each vertex v in V\C, its set of nearest neighbours in C contains at…
Maximum Cut on Interval Graphs of Interval Count Two is NP-complete
Alexey Barsukov, Bodhayan Roy
An interval graph has interval count if it has an interval model, where among every intervals there are two that have the same length. Maximum Cut on interval graph…
Art Gallery Plus Single Specular-reflection
Arash Vaezi, Bodhayan Roy, Mohammad Ghodsi
Given a simple polygon , in the Art Gallery problem, the goal is to find the minimum number of guards needed to cover the entire , where a guard is a point and can…
Visibility Extension via Reflection
Arash Vaezi, Bodhayan Roy, Mohammad Ghodsi
This paper studies a variant of the Art Gallery problem in which the ``walls" can be replaced by \emph{reflecting edges}, which allows the guards to see further and thereby see a l…
Complexity of Maximum Cut on Interval Graphs
Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee +1
We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.