POLYNOMIAL OBSERVABLES IN THE GRAPH PARTITIONING PROBLEM
| Autor: | M. A. Marchisio |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Phase transition
Condensed Matter (cond-mat) Graph partition FOS: Physical sciences General Physics and Astronomy Statistical and Nonlinear Physics Observable Condensed Matter Computer Science Applications Combinatorics Computational Theory and Mathematics Graph (abstract data type) Mathematical Physics Mathematics |
| Zdroj: | International Journal of Modern Physics C. 12:13-18 |
| ISSN: | 1793-6586 0129-1831 |
| DOI: | 10.1142/s0129183101001456 |
| Popis: | Although NP-Complete problems are the most difficult decisional problems, it is possible to discover in them polynomial (or easy) observables. We study the Graph Partitioning Problem showing that it is possible to recognize in it two correlated polynomial observables. The particular behaviour of one of them with respect to the connectivity of the graph suggests the presence of a phase transition in partitionability. Comment: 7 pages, 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|