M. Dyer, A. Frieze, and M. Jerrum,
Approximately counting Hamiltonian paths and cycles in dense graphs,
Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1994,
and
Technical Report ECS-LFCS-93-259, Department of Computer Science,
University of Edinburgh, April 1993.
A. Frieze, M. Jerrum, M. Molloy, R. Robinson, and N. Wormald,
Generating and counting Hamilton cycles in random regular graphs,
Technical Report ECS-LFCS-94-313, Department of Computer Science,
University of Edinburgh, December 1994.
M. Jerrum and A. Sinclair,
Fast uniform generation of regular graphs,
Theoretcal Computer Science, 73:91-100, 1990.
M. R. Jerrum, L. G. Valiant, and V. V. Vazirani,
Random generation of combinatorial structures from a uniform distribution,
Theoretcal Computer Science, 43:169-188, 1986.
B. D. McKay and N. C. Wormald,
Uniform generation of random regular graphs of moderate degree,
Journal of Algorithms, 11:52-67, 1990.
M. Jerrum and G. Sorokin,
Simulated annealing for graph bisection
in Proceedings of the 34th IEEE Symposium on Foundations of Computer Science
(FOCS), 1993, and also
Technical Report ECS-LFCS-93-260, Department of Computer Science,
University of Edinburgh, April 1993.
Estimating the Number of k-colorings of a Graph
(Artur Czumaj
(artur))
Literatur:
M. Jerrum, A Very Simple Algorithm for Estimating the Number of k-colourings
of a Low-degree Graph, Random Structures and Algorithms, 7(2):157-165, 1995,
and also
Technical Report ECS-LFCS-94-290, Department of Computer Science,
University of Edinburgh, April 1994.
D. Gillman,
A Chernoff bound for random walks on expander graphs,
in Proceedings of the 34th IEEE Symposium on Foundations of Computer Science
(FOCS), 1993.