An extension of path coupling and its application to the Glauber dynamics for graph colorings
UNSPECIFIED. (2000) An extension of path coupling and its application to the Glauber dynamics for graph colorings. SIAM JOURNAL ON COMPUTING, 30 (6). pp. 1962-1975. ISSN 0097-5397Full text not available from this repository.
A new method for analyzing the mixing time of Markov chains is described. This method is an extension of path coupling and involves analyzing the coupling over multiple steps. The expected behavior of the coupling at a certain stopping time is used to bound the expected behavior of the coupling after a fixed number of steps. The new method is applied to analyze the mixing time of the Glauber dynamics for graph colorings. We show that the Glauber dynamics has O(n log(n)) mixing time for triangle-free Delta -regular graphs if k colors are used, where k greater than or equal to (2 - eta)Delta, for some small positive constant eta. This is the rst proof of an optimal upper bound for the mixing time of the Glauber dynamics for some values of k in the range k less than or equal to 2 Delta.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Journal or Publication Title:||SIAM JOURNAL ON COMPUTING|
|Official Date:||18 April 2000|
|Number of Pages:||14|
|Page Range:||pp. 1962-1975|
Actions (login required)