Network conduciveness with application to the graph-coloring and independent-set optimization transitions

Details Network conduciveness with application to the graph-coloring and independent-set optimization transitions Network conduciveness with application to the graph-coloring and independent-set optimization transitions

2010-03-06

arxiv.org/abs/1003.1412v1

PLoS ONE 5 (2010), e11232

Physics

Condensed Matter

Statistical Mechanics

Scientific paper

10.1371/journal.pone.0011232

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 exemplify its use through an application to the two problems in combinatorial optimization that, given an undirected graph, ask that its so-called chromatic and independence numbers be found. Though NP-hard, when solved on sequences of expanding random graphs there appear marked transitions at which optimal solutions can be obtained substantially more easily than right before them. We demonstrate that these phenomena 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. At the said transitions, this network becomes strikingly more conducive in the direction of the optimal solutions than it was just before them, while at the same time becoming less conducive in the opposite direction. We believe that, besides becoming useful also in other areas in which network theory has a role to play, network conduciveness may become instrumental in helping clarify further issues related to NP-hardness that remain poorly understood.

Affiliated with

Also associated with

No associations

Rating

Network conduciveness with application to the graph-coloring and independent-set optimization transitions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Network conduciveness with application to the graph-coloring and independent-set optimization transitions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network conduciveness with application to the graph-coloring and independent-set optimization transitions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-270365