The Minset-Poset Approach to Representations of Graph Connectivity

摘要

Various instances of the minimal-set poset (minset-poset for short) have been proposed in the literature, e.g., the representation of Picard and Queyranne for all st-minimum cuts of a flow network. We begin with an explanation of why this poset structure is common. We show any family of sets F that can be defined by a "labelling algorithm" (e.g., the Ford-Fulkerson labelling algorithm for maximum network flow) has an algorithm that constructs the minset poset for F. We implement this algorithm to efficiently find the nodes of the poset when F is the family of minimum edge cuts of an unweighted graph; we also give related algorithms to construct the entire poset for weighted graphs. The rest of the article discusses applications to edge-and vertex connectivity, both combinatorial and algorithmic, that we now describe.