4 citations · 4 across the 10 of their papers we have counts for
18 papers
Hardness of Vertex Splitting: Cographs, Chordal Graphs, and Beyond
Satyabrata Jana, Shivesh K. Roy, R. B. Sandeep
Vertex splitting replaces a vertex (v) by two nonadjacent vertices whose neighborhoods together equal (N(v)). A split is \emph{exclusive} if these neighborhoods are disjoint and \e…
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…
FPT Approximations for Connected Maximum Coverage
Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu +3
We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set. Given a red-blue bipartite graph and an auxiliary connectivity…
Exotic coupled spin-charge states in decorated honeycomb magnets: A hybrid-Monte Carlo study
Satyabrata Jana, Sahinur Reja
We uncover four exotic coupled spin-charge ground states in the strong coupling limit of the Kondo lattice model at various electronic fillings on a frustrated decorated honeycomb…
Witness Set in Monotone Polygons: Exact and Approximate
Udvas Das, Binayak Dutta, Satyabrata Jana +2
Given a simple polygon , two points and within are {\em visible} to each other if the line segment between and is contained in $\mathscr{…
Towards Transitive-free Digraphs
Ankit Abhinav, Satyabrata Jana, Abhishek Sahu
In a digraph , an arc in is considered transitive if there is a path from to in . A digraph is transitive-free if it does not contain any transitive…
A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
Satyabrata Jana, Lawqueen Kanesh, Madhumita Kundu +2
In the Subset Feedback Arc Set in Tournaments, Subset-FAST problem we are given as input a tournament with a vertex set and an arc set , along with a terminal set…
Multivariate Exploration of Metric Dilation
Aritra Banik, Fedor V. Fomin, Petr A. Golovach +3
Let be a weighted graph embedded in a metric space . The vertices of correspond to the points in , with the weight of each edge being the distance $d_M…
On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
Václav Blažej, Satyabrata Jana, M. S. Ramanujan +1
In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure…
Cuts in Graphs with Matroid Constraints
Aritra Banik, Fedor V. Fomin, Petr A. Golovach +3
{\sc Vertex -Cut} and {\sc Vertex Multiway Cut} are two fundamental graph separation problems in algorithmic graph theory. We study matroidal generalizations of these probl…
A Polynomial Kernel for Proper Helly Circular-arc Vertex Deletion
Akanksha Agrawal, Satyabrata Jana, Abhishek Sahu
A proper Helly circular-arc graph is an intersection graph of a set of arcs on a circle such that none of the arcs properly contains any other arc and every set of pairwise interse…
Parameterized algorithms for Eccentricity Shortest Path Problem
Sriram Bhyravarapu, Satyabrata Jana, Lawqueen Kanesh +2
Given an undirected graph and an integer , the Eccentricity Shortest Path (ESP) asks to find a shortest path such that for every vertex , there is a…
Linear Size Planar Manhattan Network for Convex Point Sets
Satyabrata Jana, Anil Maheshwari, Sasanka Roy
Let be an edge-weighted geometric graph such that every edge is horizontal or vertical. The weight of an edge is its length. Let denote the len…
Balanced Connected Subgraph Problem in Geometric Intersection Graphs
Sujoy Bhore, Satyabrata Jana, Supantha Pandit +1
We study the Balanced Connected Subgraph(shortly, BCS) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Gi…
Maximum Bipartite Subgraph of Geometric Intersection Graphs
Satyabrata Jana, Anil Maheshwari, Saeed Mehrabi +1
We study the Maximum Bipartite Subgraph (MBS) problem, which is defined as follows. Given a set of geometric objects in the plane, we want to compute a maximum-size subset…
The Balanced Connected Subgraph Problem
Sujoy Bhore, Sourav Chakraborty, Satyabrata Jana +3
The problem of computing induced subgraphs that satisfy some specified restrictions arises in various applications of graph algorithms and has been well studied. In this paper, we…
Covering and Packing of Rectilinear Subdivision
Satyabrata Jana, Supantha Pandit
We study a class of geometric covering and packing problems for bounded regions on the plane. We are given a set of axis-parallel line segments that induces a planar subdivision wi…
Uniquely Restricted Matchings in Interval Graphs
Mathew C. Francis, Dalu Jacob, Satyabrata Jana
A matching in a graph is said to be uniquely restricted if there is no other matching in that matches the same set of vertices as . We describe a polynomial-time alg…