The Library
An extension of path coupling and its application to the Glauber dynamics for graph colorings
Tools
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-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
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 | ||||
Publisher: | SIAM PUBLICATIONS | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 18 April 2000 | ||||
Dates: |
|
||||
Volume: | 30 | ||||
Number: | 6 | ||||
Number of Pages: | 14 | ||||
Page Range: | pp. 1962-1975 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |