𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Lower bounds for on-line graph coloring

✍ Scribed by Magnus M. Halldórsson; Mario Szegedy

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
771 KB
Volume
130
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Graph coloring bounds for cellular radio
Graph coloring bounds for cellular radio
✍ Pierre Baldi; Edward C. Posner 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 321 KB

A graph coloring problem usdul in deciding whether a set of call requests in cellular radio is compatible with frequency use constraints is introduced. Lower and upper bounds are obtained for the hexagonal cell case typical of raany urban cellular systems. These bounds are on the number of frequenci

Parallel and On-Line Graph Coloring
Parallel and On-Line Graph Coloring
✍ Magnus M Halldórsson 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 209 KB

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

Lower bounds for line stabbing
Lower bounds for line stabbing
✍ D. Avis; J.M. Robert; R. Wenger 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 721 KB