Document Detail

Network conduciveness with application to the graph-coloring and independent-set optimization transitions.
MedLine Citation:
PMID:  20628597     Owner:  NLM     Status:  MEDLINE    
BACKGROUND: Given an undirected graph, we consider the two problems of combinatorial optimization, which ask that its chromatic and independence numbers be found. Although both problems are NP-hard, when either one is solved on the incrementally denser graphs of a random sequence, at certain critical values of the number of edges, it happens that the transition to the next value causes optimal solutions to be obtainable substantially more easily than right before it. METHODOLOGY/PRINCIPAL FINDINGS: We introduce the notion of a network's conduciveness, a probabilistically interpretable measure of how the network's structure allows it to be conducive to roaming agents, in certain conditions, from one portion of the network to another. We demonstrate that the performance jumps of graph coloring and independent sets at the critical-value transitions in the number of edges can be understood by resorting to the network that represents the solution space of the problems for each graph and examining its conduciveness between the non-optimal solutions and the optimal ones. Right past each transition, this network becomes strikingly more conducive in the direction of the optimal solutions than it was just before it, while at the same time becoming less conducive in the opposite direction. CONCLUSIONS/SIGNIFICANCE: Network conduciveness provides a useful conceptual framework for explaining the performance jumps associated with graph coloring and independent sets. We believe it may also become instrumental in helping clarify further issues related to NP-hardness that remain poorly understood. Additionally, it may become useful also in other areas in which network theory has a role to play.
Valmir C Barbosa
Related Documents :
22285097 - Dynamics of a climbing surfactant-laden film - i: base-state flow.
11308527 - Effect of the accelerating growth of communications networks on their structure.
16526487 - An analog silicon retina with multichip configuration.
7827417 - Steady-state coexistence of three pure and simple competitors in a four-membered reacto...
20867267 - Supersolid phases in a realistic three-dimensional spin model.
19254727 - Reliability of regulatory networks and its evolution.
Publication Detail:
Type:  Journal Article; Research Support, Non-U.S. Gov't     Date:  2010-07-08
Journal Detail:
Title:  PloS one     Volume:  5     ISSN:  1932-6203     ISO Abbreviation:  PLoS ONE     Publication Date:  2010  
Date Detail:
Created Date:  2010-07-14     Completed Date:  2010-10-28     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  101285081     Medline TA:  PLoS One     Country:  United States    
Other Details:
Languages:  eng     Pagination:  e11232     Citation Subset:  IM    
Programa de Engenharia de Sistemas e Computação, Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia (COPPE), Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Computer Simulation*
Data Interpretation, Statistical*
Models, Statistical*

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine

Previous Document:  Modified vaccinia virus ankara exerts potent immune modulatory activities in a murine model.
Next Document:  Common polymorphisms in MTNR1B, G6PC2 and GCK are associated with increased fasting plasma glucose a...