375 citations · 494 across the 29 of their papers we have counts for
4 papers · 1 filter
Space-Efficient FPT Algorithms
Arindam Biswas, Venkatesh Raman, Srinivasa Rao Satti +1
We prove algorithmic results showing that a number of natural parameterized problems are in the restricted-space parameterized classes Para-L and FPT+XL. The first class comprises…
Structural Parameterizations of Budgeted Graph Coloring
Susobhan Bandopadhyay, Suman Banerjee, Aritra Banik +1
We introduce a variant of the graph coloring problem, which we denote as {\sc Budgeted Coloring Problem} (\bcp). Given a graph , an integer and an ordered list of integers $…
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…
Deletion to Scattered Graph Classes I -- case of finite number of graph classes
Ashwin Jacob, Jari J. H. de Kroon, Diptapriyo Majumdar +1
Graph-modification problems, where we modify a graph by adding or deleting vertices or edges or contracting edges to obtain a graph in a {\it simpler} class, is a well-studied opti…