20 citations · 27 across the 3 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2011★ 20 cited
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
Andreas Galanis, Qi Ge, Daniel Stefankovic +2
We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Delta. More generally, for an input graph G=(V,E) and…
cs.CC2010
The Complexity of Counting Eulerian Tours in 4-Regular Graphs
Qi Ge, Daniel Stefankovic
We investigate the complexity of counting Eulerian tours ({\sc #ET}) and its variations from two perspectives---the complexity of exact counting and the complexity w.r.t. approxima…