MINIMUM-WEIGHT CYCLES IN 3-SEPARABLE GRAPHS

Authors
COULLARD CR GARDNER LL WAGNER DK
Citation
Cr. Coullard et al., MINIMUM-WEIGHT CYCLES IN 3-SEPARABLE GRAPHS, Networks, 29(3), 1997, pp. 151-160
Citations number
19
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
29
Issue
3
Year of publication
1997
Pages
151 - 160
Database
ISI
SICI code
0028-3045(1997)29:3<151:MCI3G>2.0.ZU;2-6
Abstract
This paper presents a polynomial-time algorithm for the minimum-weight -cycle problem on graphs that decompose via 3-separations into well-st ructured graphs. The problem is NP-hard in general. Graphs that decomp ose 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 run s in linear time. (C) 1997 Jonn Wiley & Sons, Inc.