The graph coloring problem is the following: COLORING: Data: adjacency matrix M of an m-vertex undirected graph.
Fantastic news! We've Found the answer you've been seeking!
Question:
COLORING:
Data: adjacency matrix M of an m-vertex undirected graph.
Decide: if there exists a vector v € {bleu, rouge, vert}msuch that for every edge (a, b) in the graph, v[a] v[b].
a- Sketch a backtracking algorithm colo(M) for Coloring. Hint. Think of what might be a k-promising vector, 0 Sk Sm.
b- Even if no deterministic polynomial time algorithm solving Coloring is known, could you turn your algorithm above into a polynomial time Las Vegas algorithm? (Explain.)
Related Book For
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi
Posted Date: