Soft x-ray diffraction of striated muscle
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Kellerman has presented a method for determining keyword conflicts and described a heuristic algorithm which solves a certain combinatorial optimization problem in connection with this method. This optimization problem is here shown to be equivalent to the problem of covering the edges of a graph by complete subgraphs with the objective of minimizing the number of complete subgraphs. A relationship between this edge-clique-cover problem and the graph coloring problem is established which allows algorithms for either one of these problems to be constructed from algorithms for the other. As consequences of this relationship, the keyword conflict problem and the edge-clique-cover problem are shown to be NP-complete, and if P ≠ NP then they do not admit polynomial-time approximation algorithms which always produce solutions within a factor less than 2 from the optimum. © 1978, ACM. All rights reserved.
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Daniel M. Bikel, Vittorio Castelli
ACL 2008
Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)