Approximately counting Hamilton paths and cycles in dense graphs

被引：20

作者：

Dyer, M ^{[1
]}

Frieze, A

Jerrum, M

机构：

[1] Univ Leeds, Sch Comp Studies, Leeds LS2 9JT, W Yorkshire, England

[2] Carnegie Mellon Univ, Dept Math, Pittsburgh, PA 15213 USA

[3] Univ Edinburgh, Dept Comp Sci, Edinburgh EH9 3JZ, Midlothian, Scotland

[4] NEC Res Inst, Princeton, NJ 08540 USA

来源：

SIAM JOURNAL ON COMPUTING | 1998年 / 27卷 / 05期

关键词：

Hamilton cycles; fpras; dense;

D O I：

10.1137/S009753979426112X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We describe fully polynomial randomized approximation schemes for the problems of determining the number of Hamilton paths and cycles in an n-vertex graph with minimum degree (1/2 + alpha)n, for any fixed alpha > 0. We show that the exact counting problems are #P-complete. We also describe fully polynomial randomized approximation schemes for counting paths and cycles of all sizes in such graphs.

引用

页码：1262 / 1272

页数：11

共 22 条

[1]

Annan JD., 1994, Comb. Probab. Comput, V3, P273, DOI DOI 10.1017/S0963548300001188

[2]

Bollobas B., 1978, EXTREMAL GRAPH THEOR

[3] COUNTING LINEAR EXTENSIONS [J].

BRIGHTWELL, G ;

WINKLER, P .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1991, 8 (03) :225-242

[4]

Broder Andrei Z., 1988, P 20 ANN ACM S THEOR, P551

[5]

Broder AZ, 1986, P 18 ANN ACM S THEOR, P50, DOI DOI 10.1145/12130.12136

[6]

Dirac G. A., 1952, Proc. Lond. Math. Soc, V2, P69, DOI DOI 10.1112/PLMS/S3-2.1.69

[7] A RANDOM POLYNOMIAL-TIME ALGORITHM FOR APPROXIMATING THE VOLUME OF CONVEX-BODIES [J].

DYER, M ;

FRIEZE, A ;

KANNAN, R .

JOURNAL OF THE ACM, 1991, 38 (01) :1-17

[8] ON THE COMPLEXITY OF COMPUTING THE VOLUME OF A POLYHEDRON [J].

DYER, ME ;

FRIEZE, AM .

SIAM JOURNAL ON COMPUTING, 1988, 17 (05) :967-974

[9] COUNTING THE NUMBER OF HAMILTON CYCLES IN RANDOM DIGRAPHS [J].

FRIEZE, A ;

SUEN, S .

RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (03) :235-241

[10]

FRIEZE AM, 1994, ECSLFCS94313 U ED DE

← 1 2 3 →