Optimizing partitions of percolating graphs

Stefan Boettcher

Physica A: Statistical Mechanics and its Applications, 1999, vol. 266, issue 1, 100-103

Abstract: The partitioning of random graphs is investigated numerically using “simulated annealing” and “extremal optimization”. While generally in an NP-hard problem, it is shown that the optimization of the graph partitions is particularly difficult for sparse graphs with average connectivities near the percolation threshold. At this threshold, the relative error of “simulated annealing” is found to diverge in the thermodynamic limit. On the other hand, “extremal optimization”, a new general purpose method based on self-organized criticality, produces near-optimal partitions with bounded error at any low connectivity at a comparable computational cost.

Keywords: Optimization; Graph partitioning; Percolation; Simulated annealing; Extremal optimization; Self-organized criticality (search for similar items in EconPapers)
Date: 1999
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437198005822
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

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:eee:phsmap:v:266:y:1999:i:1:p:100-103

DOI: 10.1016/S0378-4371(98)00582-2

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().