Optimal coteries for rings and related networks
Toshihide Ibaraki, Hiroshi Nagamochi, Tsunehiko Kameda · 2003
Although finding an optimal coterie for a general graph G is computationally intractable, it is shown that it can be easily found if G is a ring. Since the solution is already known when G is a complete graph, it is implied that an optimal coterie can be obtained if every biconnected component of G consists of a single edge, a ring, or a complete graph.>