A. Lahiri

collaborators

2 papers

cs.DS2019

Approximating MIS over equilateral $B_{1}$ -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 $B_{1}$ -VPG graphs. These are intersection graphs of $L$ -shaped plan…

cs.DM2019

Improved Approximation for Maximum Edge Colouring Problem

L Sunil Chandran, Abhiruk Lahiri, Nitin Singh

The anti-Ramsey number, $a r (G, H)$ is the minimum integer $k$ such that in any edge colouring of $G$ with $k$ colours there is a rainbow subgraph isomorphic to $H$ , i.e., a copy of…

Approximating MIS over equilateral B1​-VPG graphs

Improved Approximation for Maximum Edge Colouring Problem

Approximating MIS over equilateral $B_{1}$ -VPG graphs