Showing cs.DSShow all
3 papers · 1 filter
cs.DS2023
Kernelizing Problems on Planar Graphs in Sublinear Space and Polynomial Time
Arindam Biswas, Johannes Meintrup
In this paper, we devise a scheme for kernelizing, in sublinear space and polynomial time, various problems on planar graphs. The scheme exploits planarity to ensure that the resul…
cs.DS2021
Sublinear-Space Approximation Algorithms for Max r-SAT
Arindam Biswas, Venkatesh Raman
In the Max -SAT problem, the input is a CNF formula with variables where each clause is a disjunction of at most literals. The objective is to compute an assignment whic…
cs.DS2020
Approximation in (Poly-) Logarithmic Space
Arindam Biswas, Venkatesh Raman, Saket Saurabh
We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d-Hitt…