66 citations · 206 across the 36 of their papers we have counts for
Showing 2016 · cs.DSShow all
2 papers · 2 filters
cs.DS2016
Faster Graph Coloring in Polynomial Space
Serge Gaspers, Edward Lee
We present a polynomial-space algorithm that computes the number independent sets of any input graph in time for graphs with maximum degree 3 and in time $O(1.2355^n)…
cs.DS2016★ 2 cited
On Satisfiability Problems with a Linear Structure
Serge Gaspers, Christos Papadimitriou, Sigve Hortemo Saether +1
It was recently shown \cite{STV} that satisfiability is polynomially solvable when the incidence graph is an interval bipartite graph (an interval graph turned into a bipartite gra…