Premium
Minimum‐weight cycles in 3‐separable graphs
Author(s) -
Coullard Collette R.,
Gardner L. Leslie,
Wagner Donald K.
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199705)29:3<151::aid-net3>3.0.co;2-g
Subject(s) - combinatorics , mathematics , chordal graph , pathwidth , indifference graph , modular decomposition , metric dimension , minimum weight , separable space , time complexity , discrete mathematics , 1 planar graph , graph , line graph , mathematical analysis
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