54 citations · 59 across the 6 of their papers we have counts for
Showing 2017 · cs.DSShow all
3 papers · 2 filters
cs.DS2017★ 3 cited
Randomly coloring graphs of bounded treewidth
Shai Vardi
We consider the problem of sampling a proper -coloring of a graph of maximal degree uniformly at random. We describe a new Markov chain for sampling colorings, and show that…
cs.DS2017
A note on the size of query trees
Shai Vardi
We consider query trees of graphs with degree bounded by a constant, . We give simple proofs that the size of a query tree is constant in expectation and w.h.p…
cs.DS2017
On the Probe Complexity of Local Computation Algorithms
Uriel Feige, Boaz Patt-Shamir, Shai Vardi
The Local Computation Algorithms (LCA) model is a computational model aimed at problem instances with huge inputs and output. For graph problems, the input graph is accessed using…