A greedy approach can be applied to find 2 edge-disjoint 1-trees or spanning trees (if they exist) of minimum total length in a graph with n vertices and m edges. A greedy algorithm to solve the tree problem contains a routine that tests whether 2 edge-disjoint forests can be augmented with a given edge. Two test routines are discussed with different worst-case running times. The most efficient one is utilized to derive in O(mlogm+n2) operations a lower bound solution to the 2-Peripatetic Salesman Problem (2-PSP), which requires 2 edge-disjoint Hamiltonian cycles of minimum total length. Then the other test routine executes in O(n2) operations a sensitivity analysis for all relevant edges. Computational results illustrate the impact of the sensitivity analysis.
