Affordable Access

deepdyve-link deepdyve-link
Publisher Website

Rapid algorithm for identifying backbones in the two-dimensional percolation model

Authors
  • Yin, Wei-Guo
  • Tao, Ruibao
Type
Published Article
Publication Date
Jan 15, 2001
Submission Date
Dec 11, 2000
Identifiers
DOI: 10.1142/S0129183103005509
arXiv ID: cond-mat/0012169
Source
arXiv
License
Unknown
External links

Abstract

We present a rapid algorithm for identifying the current-carrying backbone in the percolation model. It applies to general two-dimensional graphs with open boundary conditions. Complemented by the modified Hoshen-Kopelman cluster labeling algorithm, our algorithm identifies dangling parts using their local properties. For planar graphs, it finds the backbone almost four times as fast as Tarjan's depth-first-search algorithm, and uses the memory of the same size as the modified Hoshen-Kopelman algorithm. Comparison with other algorithms for backbone identification is addressed.

Report this publication

Statistics

Seen <100 times