| Автор | J R Banavar |
| Автор | D Sherrington |
| Автор | N Sourlas |
| Дата выпуска | 1987-01-11 |
| dc.description | The problem of bipartitioning a random graph of fixed finite local valence (connectivity) so as to minimise the number of cross edges is studied by the application of Monte Carlo simulation of thermodynamics and annealing. This problem is NP-complete and is relevant as an idealisation of several practical organisation problems. Evidence is presented for the existence of a multiplicity of metastable states and for non-self-averaging and ultrametricity in the space of overlaps, albeit with a possible critical valence. An empirical formula is presented for the optimal cost, in excellent accord with values obtained by simulation and those known exactly. |
| Формат | application.pdf |
| Издатель | Institute of Physics Publishing |
| Название | Graph bipartitioning and statistical mechanics |
| Тип | lett |
| DOI | 10.1088/0305-4470/20/1/001 |
| Print ISSN | 0305-4470 |
| Журнал | Journal of Physics A: Mathematical and General |
| Том | 20 |
| Первая страница | L1 |
| Последняя страница | L8 |
| Аффилиация | J R Banavar; Schlumberger-Doll Res., Ridgefield, CT, USA |
| Аффилиация | D Sherrington; Schlumberger-Doll Res., Ridgefield, CT, USA |
| Аффилиация | N Sourlas; Schlumberger-Doll Res., Ridgefield, CT, USA |
| Выпуск | 1 |
