Premium
On systematic scan for sampling H‐colorings of the path
Author(s) -
Pedersen Kasper
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20243
Subject(s) - combinatorics , vertex (graph theory) , completeness (order theory) , path (computing) , mathematics , markov chain , block (permutation group theory) , algorithm , discrete mathematics , computer science , statistics , graph , mathematical analysis , programming language
We show that systematic scan for H ‐colorings of the n ‐vertex path mixes in O (log n ) scans for any fixed H using block dynamics. For a restricted family of H we furthermore show that systematic scan mixes in O (log n ) scans for any scan order. For completeness we show that a random update Markov chain mixes in O ( n log n ) updates for any fixed H . © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom