Thumbnail
Access Restriction
Subscribed

Author Wong, C. K. ♦ Kou, L. T. ♦ Stockmeyer, L. J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Polynomial-time heuristics ♦ Np-complete problems ♦ Edge clique cover ♦ Keyword conflicts ♦ Computational complexity ♦ Node clique cover ♦ Intersection graphs
Abstract 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.
Description Affiliation: IBM Thomas J. Watson Research Center, Yorktown Heights, NY (Kou, L. T.; Stockmeyer, L. J.; Wong, C. K.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 21
Issue Number 2
Page Count 5
Starting Page 135
Ending Page 139


Open content in new tab

   Open content in new tab
Source: ACM Digital Library