C. Subramanian

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…

math.CO2011

New lower bounds for the independence number of sparse graphs and hypergraphs

Kunal Dutta, Dhruv Mubayi, C. R. Subramanian

We obtain new lower bounds for the independence number of $K_{r}$ -free graphs and linear $k$ -uniform hypergraphs in terms of the degree sequence. This answers some old questions rais…

Approximating MIS over equilateral B1​-VPG graphs

New lower bounds for the independence number of sparse graphs and hypergraphs

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