9 papers · 1 filter
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…
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…
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…