𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parallel and On-Line Graph Coloring

✍ Scribed by Magnus M Halldórsson

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
209 KB
Volume
23
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We discover a surprising connection between graph coloring in two orthogonal paradigms: parallel and on-line computing. We present a randomized on-line Ž . coloring algorithm with a performance ratio of O nrlog n , an improvement of log n factor over the previous best known algorithm of Vishwanathan. Also, from

'

the same principles, we construct a parallel coloring algorithm with the same performance ratio, for the first such result. As a byproduct, we obtain a parallel approximation for the independent set problem.

📜 SIMILAR VOLUMES

Coloring quasi-line graphs
Coloring quasi-line graphs
✍ Maria Chudnovsky; Alexandra Ovetsky 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A graph __G__ is a quasi‐line graph if for every vertex __v__, the set of neighbors of __v__ can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if __G__ is a line graph, then

On-Line Coloring of Sparse Random Graphs
On-Line Coloring of Sparse Random Graphs and Random Trees
✍ Boris Pittel; Robert S. Weishaar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 164 KB

The performance of the greedy coloring algorithm ''first fit'' on sparse random graphs G and on random trees is investigated. In each case, approximately n, c r n log log n colors are used, the exact number being concentrated almost surely on at 2 most two consecutive integers for a sparse random gr

Asymmetric graph coloring games
Asymmetric graph coloring games
✍ H. A. Kierstead 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

## Abstract We introduce the (__a,b__)‐coloring game, an asymmetric version of the coloring game played by two players Alice and Bob on a finite graph, which differs from the standard version in that, in each turn, Alice colors __a__ vertices and Bob colors __b__ vertices. We also introduce a relat

Parallel Heuristics for Improved, Balanc
Parallel Heuristics for Improved, Balanced Graph Colorings
✍ Robert K. Gjertsen; Jr.; Mark T. Jones; Paul E. Plassmann 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 399 KB

The computation of good, balanced graph colorings is an essential part of many algorithms required in scientific and engineering applications. Motivated by an effective sequential heuristic, we introduce a new parallel heuristic, PLF, and show that this heuristic has the same expected runtime under