Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alan Frieze:

TR04-009 | 22nd January 2004
Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda

Randomly coloring constant degree graphs

We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree &Delta;. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> &ge; <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either: ... more >>>

TR94-005 | 12th December 1994
Noga Alon, Alan Frieze, Dominic Welsh

Polynomial time randomised approximation schemes for Tutte-Gr\"{o}thendieck invariants: the dense case

The Tutte-Gr\"othendieck polynomial $T(G;x,y)$ of a graph $G$
encodes numerous interesting combinatorial quantities associated
with the graph. Its evaluation in various points in the $(x,y)$
plane give the number of spanning forests of the graph, the number
of its strongly connected orientations, the number of its proper
$k$-colorings, the (all ... more >>>

ISSN 1433-8092 | Imprint