Minimum-weight cycles in 3-separable graphs
Collette R. Coullard, Leslie L. Gardner, Donald K. Wagner · Networks · 1997
This paper presents a polynomial-time algorithm for the minimum-weight-cycle problem on graphs that decompose via 3-separations into well-structured graphs. The problem is NP-hard in general. Graphs that decompose via 3-separations into well-structured graphs include Halin, outer-facial, delta-wye, wye-delta, flat, and twirl-wheel graphs. For each of these classes of graphs, given the decomposition, the algorithm runs in linear time. © 1997 John Wiley & Sons, Inc. Networks 29: 151–160, 1997