非表示:
キーワード:
-
要旨:
We present algorithms for minimum coloring k-colorable graphs
drawn from random and semi-random models. In the first model,
each allowed edge is included with indpendent probability p.
In the second model, an adversary is given the power to
vary the edge probability as the random instance is built.
Semi-random models were introduced as a way of striking a balance
between random graphs and worst-case adversaries. Our algorithms
run in polynomial time on the average. Minimum coloring is harder
than k-coloring because even a ''short certificate'' is not presently
known for the optimality of a coloring.
