𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the minimum bounded edge-partition of a tree

✍ Scribed by Shane Dye

Book ID
108112815
Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
485 KB
Volume
157
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the uniform edge-partition of a tree
On the uniform edge-partition of a tree
✍ Bang Ye Wu; Hung-Lung Wang; Shih Ta Kuan; Kun-Mao Chao πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 197 KB
A note on the minimum label spanning tre
A note on the minimum label spanning tree
✍ Yingyu Wan; Guoliang Chen; Yinlong Xu πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 44 KB

We give a tight analysis of the greedy algorithm introduced by Krumke and Wirth for the minimum label spanning tree problem. The algorithm is shown to be a (ln(n -1) + 1)-approximation for any graph with n nodes (n > 1), which improves the known performance guarantee 2 ln n + 1.

A Note on the m-Bounded Chromatic Number
A Note on the m-Bounded Chromatic Number of a Tree
✍ Bor-Liang Chen; Ko-Wei Lih πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 77 KB

The \(m\)-bounded chromatic number of a graph \(G\) is the smallest number of colors required for a proper coloring of \(G\) in which each color is used at most \(m\) times. We will establish an exact formula for the \(m\)-bounded chromatic number of a tree.

A note on bisecting minimum spanning tre
A note on bisecting minimum spanning trees
✍ W. M. Boyce; M. R. Garey; D. S. Johnson πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 281 KB