✦ LIBER ✦

A fast algorithm for coloring Meyniel graphs

✍ Scribed by A Hertz

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 557 KB
Volume: 50
Category: Article
ISSN: 0095-8956
DOI: 10.1016/0095-8956(90)90078-e

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Fast algorithms for edge-coloring planar

Fast algorithms for edge-coloring planar graphs

✍ Marek Chrobak; Moti Yung 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 963 KB

A fast parallel algorithm to color a gra

A fast parallel algorithm to color a graph with Δ colors

✍ Mauricio Karchmer; Joseph Naor 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 502 KB

A self-stabilizing algorithm for colorin

A self-stabilizing algorithm for coloring bipartite graphs

✍ Sumit Sur; Pradip K. Srimani 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 566 KB

A linear 5-coloring algorithm of planar

A linear 5-coloring algorithm of planar graphs

✍ Norishige Chiba; Takao Nishizeki; Nobuji Saito 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 526 KB

An O(N2) algorithm for coloring perfect

An O(N2) algorithm for coloring perfect planar graphs

✍ Alan Tucker; Donna Wilson 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 501 KB

Algorithms for coloring semi-random grap

Algorithms for coloring semi-random graphs

✍ C. R. Subramanian; Martin Fürer; C. E. Veni Madhavan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 3 views

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require ␦ Ž . Ž . n ␦ ) 0 colors even for bounded chromatic k-co