3 papers
cs.DS2022
Tolerant Bipartiteness Testing in Dense Graphs
Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury +1
Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser and Ron [FOCS'96 and JACM'98]. Though…
cs.DS2021
A Faster Algorithm for Max Cut in Dense Graphs
Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury +1
We design an algorithm for approximating the size of \emph{Max Cut} in dense graphs. Given a proximity parameter , our algorithm approximates the size of \em…
cs.DS2019
Approximation Algorithms for Partially Colorable Graphs
Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury
Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For and $k \in \m…