Connectivity among a set of user entities in a network can be provided by a network level abstraction of acyclic graph (or spanning tree). The paper discusses the reconfiguration of a graph in the presence of failure of network nodes. A reconfiguration manifests as a graph fragmentation problem, whereby two or more disjoint subgraphs attempt to connect with one another to form a composite graph. Fragment interconnection requires contention resolution between fragments to avoid cycles. This paper presents two classes of contention resolution algorithms applicable for environments with potentially large number of fragments. They are based on pre-established ranking among fragments and random arbitration among fragments. The algorithms have been evaluated by simulation and compared. The algorithms are useful in supporting data multicasting across workstations and distributed computations involving data on different machines.