𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the max-weight edge coloring problem

✍ Scribed by Giorgio Lucarelli; Ioannis Milis; Vangelis T. Paschos

Publisher
Springer US
Year
2009
Tongue
English
Weight
416 KB
Volume
20
Category
Article
ISSN
1382-6905

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Parallel Algorithms for the Edge-Colorin
Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems
✍ Weifa Liang; Xiaojun Shen; Qing Hu πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 342 KB

In fact, Vizing's proof implies an O(nm) time algorithm with ⌬ Ο© 1 colors for the edge-coloring problem. However, Holyer has shown that deciding whether a graph requires ⌬ or ⌬ Ο© 1 colors is NP-complete [10]. For a multigraph G, Shannon showed that Ј(G) Υ… 3⌬/2 [16]. A number of parallel algorithms

On the edge-coloring problem for a class
On the edge-coloring problem for a class of 4-regular maps
✍ F. Jaeger; H. Shank πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 300 KB πŸ‘ 1 views

## Abstract A (plane) 4‐regular map __G__ is called __C__‐simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case Οƒ (__G__) is the smallest integer __k__ such that the curves of __G__ can be colored with __k__ colors in such a way that no two curves

Erratum: On the edge-coloring problem fo
Erratum: On the edge-coloring problem for a class of 4-regular maps
✍ F. Jaeger; H. Shank πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 37 KB πŸ‘ 1 views

On p. 272 of the above article, paragraph # 3 is incomplete. It should read as the following: Hence to prove Proposition 4 it is enough to show that the edges of Q 4 can be colored with 4 colors in such a way that each square has one edge of each color. Such a coloring is displayed on the following