Cited By
View all- Eğecioğlu ÖPeinado M(2002)Algorithms for Almost-Uniform Generation with an Unbiased Binary SourceComputing and Combinatorics10.1007/3-540-68535-9_15(117-126)Online publication date: 4-Jun-2002
Random generation of embedded graphs and an extension to Dobrushin uniqueness (extended abstract)
Pages 176 - 185
References
[1]
D. Aldous, Random walks on finite groups and rapidly mixing Markov chains, in Sgminaire de Probabilitgs XVII, Lecture Notes in Mathematics 986, pages 243-297. $pfinger-Verlag, 1982.
[2]
D, Aldous and J. Fill. Reversible Markov Chains andRandom Walks on Graphs. Book in preparation, 1995.
[3]
N, Alon, Eigenvalues and expanders. Combinatodca, 6:83- 96, 1986,
[4]
R, Bubley and M, Dyer. Path coupling: A technique for provtng rapid mixing in Markov chains. In Proe. of the 3&h Annual Symposium on Foundations of Computer Science, 1997.
[5]
R. Bubley and M. Dyer. Faster random generation of linear exten.~tons, In Proceedings of tile Ninth Annual ACM. SIAM Symposium on Discrete Algorithms, San Francisco, California, 1998,
[6]
R, Bubley, M, Dyer, and C, Greenhill. Beating the 2A bound for approximately counting coloufings: A computer-assisted proof of rapid mixing. In Proceedings of the Ninth Annual ACM.$IAM $),mposium on Discrete Algorithms, San Fran. c1$co, California, 1998,
[7]
R, L, Dobrushin. The description of a random field by means of conditional probabilities and conditions of its regularity. Theory of Probability and its Applications, 13(2):197-224, 1968,
[8]
R, L, Dobrushin. Prescribing systems of random variables by conditional distributions. Theory of Probability and its Applications, 15(3):458--486, 1970.
[9]
R, L, Dobrushin and S. B. Shlosman. Constructuve criterion for the uniqueness of Gibbs field, 1985.
[10]
M, Dyer and C. Oreenhill, On Markov chains for independent t;eta, (preprint), 1997.
[11]
$, Elliot, Physics of Amorphous Materials. Longman, 1990.
[12]
M, R, Oarey and D. S. Johnson. Computers and Intractability: a gtdde to the theory of NP.completeness. W. H. Freeman, 1979,
[13]
L, Goldberg and M, $errum. Randomly sampling molecules. In Proc, of the 8th AnnuaI ACM-SlAM Symposium on Discrete Algorithms, 1997,
[14]
V, Gore and M, Jerrum. The Swendsen-Wang process does not always mix rapidly. Technical Report ECS-LFCS-96-349, University of Edinburgh, Department of Computer Science, 1996,
[15]
M. Jerrum. A very simple algorithm for estimating the number of k-eolourings of a low-density graph. Random $truc. tures and Algorithms, 6, 1995.
[16]
M. Jerrum and A. Sinclair. Approximating the permanent. SIAM Journal on Computing, 18:1149--1178, 1989.
[17]
M. $errum and A. Sinclair. Polynomial-time approximation algorithms for the Ising model. SiAM Journal on Computing, 22(5):1087-1116, October 1993.
[18]
L.A. Levin. Average-ease complete problems. $1AMJournal on Computing, 15:285--286, 1986.
[19]
T. Lindvall. Lectures on the Coupling Method. Wiley, 1992.
[20]
M. Luby, D. Randall, and A. Sinclair. Markov chain also. rithms for planar lattice structures (extended abstract). In 36th Annual S37nposium on Foundations of Computer Science, pages 150-159, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.
[21]
N. Madras and D. Randall. Factoring graphs to bound mixing rates. In 37th Annual $3~posium on Foundations of Computer Science, pages 194--203. IEEE, 1996.
[22]
R. Motwani and P. Raghavan. Randomized Algorithms. Cam. bridge University Press, 1995.
[23]
M. Peinado and T. Lengauer. 'Go with the winners' generators with applications to molecular modeling. In J. Rolim, editor, Proceedings of the ist international ¿Orkshop on Ran. domization and Approximation Techniques in Computer Sci. ence, pages 135--149. Spfinger-Vefiag, 1997. Lecture Notes in Computer Science 1269.
[24]
J. Salas and A. Sokal. Absence of phase transition for anfiferromagnetie Potts models via the Dobmshin uniqueness theorem. Journal of Statistical Physics, 1996. (to appear).
[25]
B. Simon. The Statistical Mechanics of Lattice Gases. Princeton University Press, 1993.
[26]
A. Sinclair. Algorithms For Random Generation And Counting. Progress In Theoretical Computer Science. Birkhauser, Boston, 1993.
Index Terms
- Random generation of embedded graphs and an extension to Dobrushin uniqueness (extended abstract)
Recommendations
Restrained domination and its variants in extended supergrid graphs
AbstractDomination problem is a well-known NP-complete problem for general graphs. In this paper, we will study its three variants, including restrained, independent restrained, and restrained-step dominations. A restrained dominating set of a ...
Highlights- Extended supergrid graphs can be applied to computerized sewing machine, 3D printers, and so on.
An extension of regular supermagic graphs
A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper we consider ...
Cycle extension in edge-colored complete graphs
Let G be an edge-colored graph. The minimum color degree of G is the minimum number of different colors appearing on the edges incident with the vertices of G. In this paper, we study the existence of properly edge-colored cycles in (not necessarily ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1998 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 May 1998
Check for updates
Qualifiers
- Article
Conference
STOC98
Sponsor:
Acceptance Rates
STOC '98 Paper Acceptance Rate 75 of 169 submissions, 44%;
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 290Total Downloads
- Downloads (Last 12 months)29
- Downloads (Last 6 weeks)3
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
Cited By
View all- Eğecioğlu ÖPeinado M(2002)Algorithms for Almost-Uniform Generation with an Unbiased Binary SourceComputing and Combinatorics10.1007/3-540-68535-9_15(117-126)Online publication date: 4-Jun-2002
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in