TY - BOOK
T1 - Approximation algorithms for the k-clique covering problem
AU - Goldschmidt, O.
AU - Hochbaum, D.S.
AU - Hurkens, C.A.J.
AU - Yu, Gang
PY - 1995
Y1 - 1995
N2 - The problem of covering edges and vertices in a graph (??or in a hypergraph??) was motivated by a problem arising in the context of component assembly problem.?? The problem is, given a graph and a clique size k, fi??nd the minimum number of k-??cliques such that all edges and vertices of the graph are covered by (??included in)?? the cliques.?? This paper provides a collection of approximation algorithms for various clique sizes with proven worst-??case bounds.?? The problem has a natural extension to hypergraphs, for which we consider one particular class.?? The k-??clique covering problem can be formulated as a Set Covering
problem.?? It is shown that the algorithms we design, that exploit the structure of this special Set Covering problem, have better performance than those derived from direct applications of general purpose algorithms for the Set Covering??. In particular, these special classes of Set Covering problems can be solved with better worst??-case bounds and??/or complexity than if treated as general Set Covering problems??.
Key words??: Approximation Algorithms; Clique Covering; Set Covering; Worst Case Analysis??.
AB - The problem of covering edges and vertices in a graph (??or in a hypergraph??) was motivated by a problem arising in the context of component assembly problem.?? The problem is, given a graph and a clique size k, fi??nd the minimum number of k-??cliques such that all edges and vertices of the graph are covered by (??included in)?? the cliques.?? This paper provides a collection of approximation algorithms for various clique sizes with proven worst-??case bounds.?? The problem has a natural extension to hypergraphs, for which we consider one particular class.?? The k-??clique covering problem can be formulated as a Set Covering
problem.?? It is shown that the algorithms we design, that exploit the structure of this special Set Covering problem, have better performance than those derived from direct applications of general purpose algorithms for the Set Covering??. In particular, these special classes of Set Covering problems can be solved with better worst??-case bounds and??/or complexity than if treated as general Set Covering problems??.
Key words??: Approximation Algorithms; Clique Covering; Set Covering; Worst Case Analysis??.
M3 - Report
T3 - Memorandum COSOR
BT - Approximation algorithms for the k-clique covering problem
PB - Technische Universiteit Eindhoven
CY - Eindhoven
ER -