Research Article
Emergence of algorithmically hard phases in transportation networks
@INPROCEEDINGS{10.1109/WIOPT.2009.5291593, author={K. Y. Michael Wong and Chi Ho Yeung}, title={Emergence of algorithmically hard phases in transportation networks}, proceedings={2nd International Workshop on Physics-Inspired Paradigms in Wireless Communications and Networks}, publisher={IEEE}, proceedings_a={PHYSCOMNET}, year={2009}, month={10}, keywords={transportation networks; Resource management; Transportation}, doi={10.1109/WIOPT.2009.5291593} }- K. Y. Michael Wong
Chi Ho Yeung
Year: 2009
Emergence of algorithmically hard phases in transportation networks
PHYSCOMNET
IEEE
DOI: 10.1109/WIOPT.2009.5291593
Abstract
We study a model of transportation networks with nonlinear elements which represent local shortage of resources. Frustration arises from competition among the nodes to become satisfied. When the initial resources are uniform, algorithmically hard regimes emerge when the average availability of resources increases. These regimes are characterized by discrete fractions of satisfied nodes, resembling the Devil's staircase. Behavior similar to those in the vertex cover or close packing problems are found. When initial resources are bimodally distributed, such algorithmically hard regimes also emerge when the fraction of rich nodes increases.
Copyright © 2009–2025 IEEE
