๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Minimum-weight cycles in 3-separable graphs

โœ Scribed by Coullard, Collette R.; Gardner, L. Leslie; Wagner, Donald K.

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
136 KB
Volume
29
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

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, deltawye, wye-delta, flat, and twirl-wheel graphs. For each of these classes of graphs, given the decomposition, the algorithm runs in linear time.

๐Ÿ“œ SIMILAR VOLUMES

Minimum bandwidth problem for embedding
Minimum bandwidth problem for embedding graphs in cycles
โœ Lin, Yixun ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 98 KB ๐Ÿ‘ 2 views

For the bandwidth B(G) and the cyclic bandwidth B c (G) of a graph G, it is known that 1 2 B(G) ยฐBc (G) ยฐB(G). In this paper, the criterion conditions for two extreme cases B c (G) ร… B(G) and B c (G) ร… 1 2 B(G) are studied. From this, some exact values of B c (G) for special graphs can be obtained.

Edge disjoint Hamilton cycles in sparse
Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
โœ Bollob๏ฟฝs, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 175 KB ๐Ÿ‘ 1 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for

Long cycles passing through a specified
Long cycles passing through a specified edge in a 3-connected graph
โœ Enomoto, Hikoe; Hirohata, Kazuhide; Ota, Katsuhiro ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 80 KB ๐Ÿ‘ 2 views

We prove the following theorem: For a connected noncomplete graph Then through each edge of G there passes a cycle of length โ‰ฅ min{|V (G)|, ฯ„(G) -1}.