A VERY SIMPLE ALGORITHM FOR ESTIMATING THE NUMBER OF K-COLORINGS OF A LOW-DEGREE GRAPH

被引：177

作者：

JERRUM, M

机构：

[1] Department of Computer Science, University of Edinburgh, Edinburgh

来源：

RANDOM STRUCTURES & ALGORITHMS | 1995年 / 7卷 / 02期

关键词：

D O I：

10.1002/rsa.3240070205

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A fully polynomial randomized approximation scheme is presented for estimating the number of (vertex) k-colorings of a graph of maximum degree Delta, when k greater than or equal to 2 Delta + 1. (C) 1995 John Wiley and Sons, Inc.

引用

页码：157 / 165

页数：9

共 11 条

[1]

ALDOUS D, 1981, SPRINGER LECT NOTES, V986, P243

[2]

Bollobas B., 1978, LONDON MATH SOC MONO

[3] On colouring the nodes of a network [J].

Brooks, RL .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1941, 37 :194-197

[4]

Diaconis P., 1988, GROUP REPRESENTATION

[5]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[6] DECAY OF CORRELATIONS IN CLASSICAL LATTICE MODELS AT HIGH-TEMPERATURE [J].

GROSS, L .

COMMUNICATIONS IN MATHEMATICAL PHYSICS, 1979, 68 (01) :9-27

[7]

JERRUM M, 1995, P IMA C COMPLEX STOC, P191

[8] RANDOM GENERATION OF COMBINATORIAL STRUCTURES FROM A UNIFORM-DISTRIBUTION [J].

JERRUM, MR ;

VALIANT, LG ;

VAZIRANI, VV .

THEORETICAL COMPUTER SCIENCE, 1986, 43 (2-3) :169-188

[9]

Karp R. M., 1983, 24th Annual Symposium on Foundations of Computer Science, P56, DOI 10.1109/SFCS.1983.35

[10] ANTIFERROMAGNETIC POTTS MODELS - COMMENT [J].

LUBIN, M ;

SOKAL, AD .

PHYSICAL REVIEW LETTERS, 1993, 71 (11) :1778-1778

← 1 2 →