过分伤痛Abstract. We have developed the first hardware and software (intellectual property) metering scheme that enables reliable low overhead proofs for the number of manufactured parts and copied programs. The key idea is to make each design slightly different d
6.1 Graph Coloring
The NP-hard graph vertex coloring (GC) optimization seeks to color a given graph with as few colors as possible, such that no two adjacent vertices receive the same color.
Given a graph, our objective is to create as many as possible high quality solutions that are relatively close. By high quality, we mean that if the optimal solution is known,then all the solutions that we generate will not use any extra color. Therefore, the finger-printing techniques for GC cannot be used in this case, because they usually introduce overhead although they are very effective in creating new solutions.
