EXTENSIVE NUMERICAL SIMULATIONS OF WEIGHTED MATCHINGS - TOTAL LENGTH AND DISTRIBUTION OF LINKS IN THE OPTIMAL SOLUTION

被引：19

作者：

BRUNETTI, R

KRAUTH, W

MEZARD, M

PARISI, G

机构：

[1] UNIV ILLINOIS,NCSA,URBANA,IL 61801

[2] ECOLE NORM SUPER,PHYS THEOR LAB,F-75231 PARIS 05,FRANCE

[3] NATL INST NUCL PHYS,ROME,ITALY

来源：

EUROPHYSICS LETTERS | 1991年 / 14卷 / 04期

关键词：

D O I：

10.1209/0295-5075/14/4/002

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

We present the results of an extensive numerical simulation on weighted matching problems, simple and bipartite, in which we show the accuracy of the mean-field predictions to better than 1%. We measure the asymptotic value of the minimum total length and the distribution of the bond lengths in the optimal solution with the help of fast combinatorial algorithms.

引用

页码：295 / 301

页数：7

共 14 条

[1] GRAPH BIPARTITIONING AND STATISTICAL-MECHANICS [J].

BANAVAR, JR ;

SHERRINGTON, D ;

SOURLAS, N .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1987, 20 (01) :L1-L8

[2] ON THE GROUND-STATES OF THE FRUSTRATION MODEL OF A SPIN-GLASS BY A MATCHING METHOD OF GRAPH-THEORY [J].

BIECHE, I ;

MAYNARD, R ;

RAMMAL, R ;

UHRY, JP .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1980, 13 (08) :2553-2576

[3]

BURKARD RE, 1980, LECTURE NOTES EC MAT, V184

[4]

DAURIAC JCA, 1985, J PHYS LETT-PARIS, V46, pL180

[5] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :125-+

[6] THE CAVITY METHOD AND THE TRAVELING-SALESMAN PROBLEM [J].

KRAUTH, W ;

MEZARD, M .

EUROPHYSICS LETTERS, 1989, 8 (03) :213-218

[7]

Lawler E. L., 1985, WILEY INTERSCIENCE S

[8]

Lovasz L, 1986, ANN DISCRETE MATH

[9]

MA SK, 1982, STATISTICAL PHYSICS

[10] ON THE SOLUTION OF THE RANDOM LINK MATCHING PROBLEMS [J].

MEZARD, M ;

PARISI, G .

JOURNAL DE PHYSIQUE, 1987, 48 (09) :1451-1459

← 1 2 →