๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Deciding k-colorability in expected polynomial time

โœ Scribed by Michael Krivelevich

Book ID
104136598
Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
79 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

For every fixed k 3 we describe an algorithm for deciding k-colorability, whose expected running time in polynomial in the probability space G(n, p) of random graphs as long as the edge probability p = p(n) satisfies p(n) C/n, with C = C(k) being a sufficiently large constant.

๐Ÿ“œ SIMILAR VOLUMES

Minimum Coloring k-Colorable Graphs in P
Minimum Coloring k-Colorable Graphs in Polynomial Average Time
โœ C.R. Subramanian ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 137 KB

We present algorithms for minimum G -coloring k-colorable graphs drawn from random and semi-random models. In both models, an adversary initially splits ลฝ . the vertices into k color classes V , . . . , V of sizes โ€ n each. In the first model,