𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Linear Algorithm for Edge-Coloring Series–Parallel Multigraphs

✍ Scribed by Xiao Zhou; Hitoshi Suzuki; Takao Nishizeki

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
313 KB
Volume
20
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

Many combinatorial problems can be efficiently solved for series᎐parallel multigraphs. However, the edge-coloring problem of finding the minimum number of colors required for edge-coloring given graphs is one of a few well-known combinatorial problems for which no efficient algorithms have been obtained for series᎐parallel multigraphs. This paper gives a linear algorithm for the problem on series᎐parallel multigraphs.

📜 SIMILAR VOLUMES

An NC Parallel Algorithm for Edge-Colori
An NC Parallel Algorithm for Edge-Coloring Series–Parallel Multigraphs
✍ Xiao Zhou; Hitoshi Suzuki; Takao Nishizeki 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 254 KB

Many combinatorial problems can be efficiently solved in parallel for series᎐parallel multigraphs. The edge-coloring problem is one of a few combinatorial problems for which no NC parallel algorithm has been obtained for series᎐parallel multigraphs. This paper gives an NC parallel algorithm for the

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

A Parallel Algorithm for Linear Programs
A Parallel Algorithm for Linear Programs with an Additional Reverse Convex Constraint
✍ Shih-Mim Liu; G.P. Papavassilopoulos 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 211 KB

A parallel method for globally minimizing a linear program with an additional reverse convex constraint is proposed which combines the outer approximation technique and the cutting plane method. Basically p (≤n) processors are used for a problem with n variables and a globally optimal solution is fo