A MODEL OF GRAPH COLORING DYNAMICS WITH ATTENTION WAVES AND STRATEGIC WAITING

Borislav Hadzhiev, Katja Windt, Werner Bergholz and Marc-Thorsten Hütt ()
Additional contact information
Borislav Hadzhiev: School of Engineering and Science, Jacobs University Bremen, Campus Ring 1, D-28759 Bremen, Germany
Katja Windt: School of Engineering and Science, Jacobs University Bremen, Campus Ring 1, D-28759 Bremen, Germany
Werner Bergholz: School of Engineering and Science, Jacobs University Bremen, Campus Ring 1, D-28759 Bremen, Germany
Marc-Thorsten Hütt: School of Engineering and Science, Jacobs University Bremen, Campus Ring 1, D-28759 Bremen, Germany

Advances in Complex Systems (ACS), 2009, vol. 12, issue 06, 549-564

Abstract: Recently, Kearnset al.[Kearns, M., Suri, S. and Montfort, N., An experimental study of the coloring problem on human subject networks,Science313(2006) 824–827] studied the topology dependence of graph coloring dynamics. In their empirical study, the authors analyze, how a network of human subjects acting as autonomous agents performs in solving a conflict-avoidance task (the graph coloring problem) for different network architectures. A surprising result was that the run-time of theempiricaldynamics decreases with the number of shortcuts in a Watts–Strogatz small-world graph. In a simulation of the dynamics based on randomly selecting color conflicts for update, they observe a strong increase of the run-time with the number of shortcuts. Here, we propose classes of strategies, which are capable of explaining the decrease in run-time with an increasing number of shortcuts. We show that the agent's strategy, the graph topology, and the complexity of the problem (essentially given by the graph's chromatic number) interact nontrivially yielding unexpected insights into the problem-solving capacity of organizational structures.

Keywords: Graph coloring; small-world graphs; job shop scheduling; excitable dynamics (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219525909002386
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:acsxxx:v:12:y:2009:i:06:n:s0219525909002386

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219525909002386

Access Statistics for this article

Advances in Complex Systems (ACS) is currently edited by Frank Schweitzer

More articles in Advances in Complex Systems (ACS) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().