Compare.alg
Last Edited by: Spreitzer, July 9, 1984 2:42:53 pm PDT
Other Algorithm:
Q ← all blocks in partition
WHILE Q not empty
Pop I from Q
FOR each neighboring block J
Split by I
Put pieces in Q (except largest, if J wasn't in Q)
Basic Gemini Algorithm:
WHILE Exist non-unique vertices
Recolor non-unique vertices
Modifications
1. Frontier Optimization. Frontier(v) = non-unique(v) & Exists newly unique neighbor. Recolor only frontier vertices, unless that makes no progress.
2. Handle automorphisms and shortcoming. Choose pairs to identify, don't backtrack.
3. Differences. When unbalanced partitions occur, make them invisible to coloring function.
Refined Algorithm:
Q ← all non-unique vertices
WHILE Exist non-unique vertices
F ← empty
FOR each v in Q:
Recolor v
FOR each v in Q:
IF v unique THEN add non-unique neighbors to F
IF F non-empty THEN Q ← F
ELSE IF progress OR Q wasn't all non-uniques THEN Q ← all non-unique vertices
ELSE {
Q ← pairs from all non-suspect colors
IF Q empty THEN Q ← pairs from all suspect colors
IF Q empty THEN EXIT}