8 citations · 10 across the 3 of their papers we have counts for
3 papers · 1 filter
Approximating MIS over equilateral -VPG graphs
Abhiruk Lahiri, Joydeep Mukherjee, C. R. Subramanian
We present an approximation algorithm for the maximum independent set (MIS) problem over the class of equilateral -VPG graphs. These are intersection graphs of -shaped plan…
A 2-Approximation Algorithm for Feedback Vertex Set in Tournaments
Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee +3
A {\em tournament} is a directed graph such that every pair of vertices is connected by an arc. A {\em feedback vertex set} is a set of vertices in such that is…
Improved Approximation Algorithms for Stochastic Matching
Marek Adamczyk, Fabrizio Grandoni, Joydeep Mukherjee
In this paper we consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. We are given an undirected graph in which every…