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

CREATORValmir C. Barbosa
YEAR2010
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
LICENSECreative Commons Attribution License
RIGHTSCC BY
SOURCEPLOS ONE

Source: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0011232

Browse the full library · About the Tower of Babel