Network Conduciveness with Application to the Graph-Coloring and Independent-Set Optimization Transitions
Valmir C. Barbosa · 2010
Read Network Conduciveness with Application to the Graph-Coloring and Independent-Set Optimization Transitions by Valmir C. Barbosa (2010) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/plos-pone-0011232.txt.
Description
Barbosa proposed a network measure in PLOS ONE in 2010. Some puzzle like problems, such as coloring a map so neighbors differ, are far easier on certain networks than others. The author named that helpful quality conduciveness and tested it on coloring and independent set problems.
The measure aims to predict when a hard problem will yield to solvers quickly. That could save computing time by matching methods to networks in advance. It offers algorithm designers a new lens on why instances differ so much in difficulty. The idea links network shape to the phase changes known in optimization problems.
Catalog record
| CREATOR | Valmir C. Barbosa |
|---|---|
| YEAR | 2010 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| LICENSE | Creative Commons Attribution License |
| RIGHTS | CC BY |
| SOURCE | PLOS ONE |
Source: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0011232