3 papers
cs.DS2021
On subgraph complementation to H-free graphs
Dhanyamol Antony, Jay Garchar, Sagartanu Pal +3
For a class of graphs, the problem SUBGRAPH COMPLEMENT TO asks whether one can find a subset of vertices of the input graph such that complement…
cs.DS2018
A Polynomial Kernel for Diamond-Free Editing
Yixin Cao, Ashutosh Rai, R. B. Sandeep +1
An -free editing problem asks whether we can edit at most edges to make a graph contain no induced copy of the fixed graph . We obtain a polynomial kernel for this proble…
cs.CC2016
Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
Yixin Cao, R. B. Sandeep
Given an sparse symmetric matrix with nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values. To maintain the matrix sparse, we would l…