Invasion percolation through minimum-weight spanning trees

Invasion percolation is often used to simulate capillary- dominated drainage and imbibition in pore networks. More than a decade ago it was observed that the part of a pore network that is involved in an invasion bond percolation is a minimum- weight spanning tree of the network, where the weights indicate resistances associated with the bonds. Thus, one can determine a minimum- weight spanning tree first and then run the invasion bond percolation on the minimum- weight spanning tree. The time complexities of the two steps are O( m alpha( m, n)) and O(n), respectively, where m is the number of edges, n is the number of vertices, and alpha(.,.) denotes the inverse Ackermann function. In this paper we ( 1 ) formulate the property of minimum- weight spanning trees that justifies the two- step approach to invasion bond percolation, ( 2 ) extend the two- step approach to invasion site percolation, and ( 3 ) further extend it to simulations of drainage ( imbibition ) that include trapping of the wetting ( nonwetting ) phase. In case of imbibition we also take snap- off into account. As a consequence, all these simulations can now be done in O( m alpha ( m, n )).