Math @ Duke
|
Publications [#10385] of Mark Huber
Preprints
- James A. Fill, Mark L. Huber, Linear expected time perfect generation of proper colorings of low degree graphs
(2008)
(last updated on 2008/08/18)
Abstract: A proper coloring assigns colors to nodes of a graph so
that no two endpoints of an edge receive the same color.
Here we present the first algorithm for sampling uniformly
from the set of proper colorings of a graph (in expected
linear time) when the number of colors is linear in the
maximum degree of the graph.
|
|
dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
| |
Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320
|
|