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

Cycles in weighted graphs

โœ Scribed by J. A. Bondy; Genghua Fan

Book ID
105117071
Publisher
Springer-Verlag
Year
1991
Tongue
English
Weight
602 KB
Volume
11
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Heavy cycles passing through some specif
Heavy cycles passing through some specified vertices in weighted graphs
โœ Jun Fujisawa; Kiyoshi Yoshimoto; Shenggui Zhang ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 111 KB

## Abstract A weighted graph is one in which every edge __e__ is assigned a nonnegative number, called the weight of __e__. The sum of the weights of the edges incident with a vertex ฯ… is called the weighted degree of ฯ…. The weight of a cycle is defined as the sum of the weights of its edges. In th

Heavy cycles and spanning trees with few
Heavy cycles and spanning trees with few leaves in weighted graphs
โœ Binlong Li; Shenggui Zhang ๐Ÿ“‚ Article ๐Ÿ“… 2011 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 205 KB

Let G be a 2-connected weighted graph and k โ‰ฅ 2 an integer. In this note we prove that if the sum of the weighted degrees of every k + 1 pairwise nonadjacent vertices is at least m, then G contains either a cycle of weight at least 2m/(k + 1) or a spanning tree with no more than k leaves.

Minimum-weight cycles in 3-separable gra
Minimum-weight cycles in 3-separable graphs
โœ Coullard, Collette R.; Gardner, L. Leslie; Wagner, Donald K. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 136 KB ๐Ÿ‘ 2 views

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, w