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

Full text not available from this repository.

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
Date:	18 April 2000
Volume:	30
Number:	6
Number of Pages:	14
Page Range:	pp. 1962-1975
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/12106

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item