{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T23:31:54Z","timestamp":1675467114436},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/2"]},{"name":"PIAF","award":["NI 369\/4"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,2]]},"abstract":"To cover the edges of a graph with a minimum number of cliques is an NP-hard problem with many applications. For this problem we develop efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive time. This is confirmed by experiments with real-world and synthetic data. Moreover, we prove the fixed-parameter tractability of covering edges by cliques.<\/jats:p>","DOI":"10.1145\/1412228.1412236","type":"journal-article","created":{"date-parts":[[2008,10,7]],"date-time":"2008-10-07T12:48:29Z","timestamp":1223383709000},"source":"Crossref","is-referenced-by-count":33,"title":["Data reduction and exact algorithms for clique cover"],"prefix":"10.1145","volume":"13","author":[{"given":"Jens","family":"Gramm","sequence":"first","affiliation":[{"name":"Eberhard-Karls-Universit\u00e4t T\u00fcbingen, T\u00fcbingen, Germany"}]},{"given":"Jiong","family":"Guo","sequence":"additional","affiliation":[{"name":"Friedrich-Schiller-Universit\u00e4t Jena, Jena, Germany"}]},{"given":"Falk","family":"H\u00fcffner","sequence":"additional","affiliation":[{"name":"Friedrich-Schiller-Universit\u00e4t Jena, Jena, Germany"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"Friedrich-Schiller-Universit\u00e4t Jena, Jena, Germany"}]}],"member":"320","published-online":{"date-parts":[[2009,2,23]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"347","article-title":"Can visibility graphs be represented compactly? Discrete","volume":"12","author":"Agarwal P. K.","year":"1994","unstructured":"Agarwal , P. K. , Alon , N. , Aronov , B. , and Suri , S. 1994 . Can visibility graphs be represented compactly? Discrete Comput. Geo. 12 , 347 -- 365 . Agarwal, P. K., Alon, N., Aronov, B., and Suri, S. 1994. Can visibility graphs be represented compactly? Discrete Comput. Geo. 12, 347--365.","journal-title":"Comput. Geo."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990309"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-006-0045-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Ausiello G. Crescenzi P. Gambosi G. Kann V. Marchetti-Spaccamela A. and Protasi M. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer New York. Ausiello G. Crescenzi P. Gambosi G. Kann V. Marchetti-Spaccamela A. and Protasi M. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer New York.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(95)00020-8"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 27th WG. LNCS","volume":"2204","author":"Chang M.-S.","unstructured":"Chang , M.-S. and M\u00fcller , H . 2001. On the tree-degree of graphs . In Proceedings of the 27th WG. LNCS , vol. 2204 . Springer, New York. 44--54. Chang, M.-S. and M\u00fcller, H. 2001. On the tree-degree of graphs. In Proceedings of the 27th WG. LNCS, vol. 2204. Springer, New York. 44--54."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer New York. Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-014-3"},{"key":"e_1_2_1_11_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer-Verlag New York. Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer-Verlag New York."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192522"},{"key":"e_1_2_1_13_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman San Francisco CA. Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman San Francisco CA."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2006.09.035"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.03.007"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90168-H"},{"key":"e_1_2_1_18_1","first-page":"187","article-title":"Complexity of graph covering problems for graphs of low degree","volume":"11","author":"Hoover D. N.","year":"1992","unstructured":"Hoover , D. N. 1992 . Complexity of graph covering problems for graphs of low degree . J. Combinatorial Math. Combinatorial Comput. 11 , 187 -- 208 . Hoover, D. N. 1992. Complexity of graph covering problems for graphs of low degree. J. Combinatorial Math. Combinatorial Comput. 11, 187--208.","journal-title":"J. Combinatorial Math. Combinatorial Comput."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90165-E"},{"key":"e_1_2_1_20_1","first-page":"544","article-title":"Determination of keyword conflict","volume":"16","author":"Kellerman E.","year":"1973","unstructured":"Kellerman , E. 1973 . Determination of keyword conflict . IBM Tech. Disclosure Bull. 16 , 2, 544 -- 546 . Kellerman, E. 1973. Determination of keyword conflict. IBM Tech. Disclosure Bull. 16, 2, 544--546.","journal-title":"IBM Tech. Disclosure Bull."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00286-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359346"},{"key":"e_1_2_1_23_1","unstructured":"Leroy X. Vouillon J. Doligez D. etal 1996. The Objective Caml System. Available on the web. http:\/\/caml.inria.fr\/ocaml\/. Leroy X. Vouillon J. Doligez D. et al. 1996. The Objective Caml System. Available on the web. http:\/\/caml.inria.fr\/ocaml\/."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_25_1","first-page":"151","article-title":"Clique covering of chordal graphs","volume":"36","author":"Ma S.","year":"1989","unstructured":"Ma , S. , Wallis , W. D. , and Wu , J. 1989 . Clique covering of chordal graphs . Utilitas Math. 36 , 151 -- 152 . Ma, S., Wallis, W. D., and Wu, J. 1989. Clique covering of chordal graphs. Utilitas Math. 36, 151--152.","journal-title":"Utilitas Math."},{"key":"e_1_2_1_26_1","series-title":"SIAM Monographs on Discrete Mathematics and Applications. SIAM","volume-title":"Topics in Intersection Graph Theory","author":"McKee T. A.","unstructured":"McKee , T. A. and McMorris , F. R. 1999. Topics in Intersection Graph Theory . SIAM Monographs on Discrete Mathematics and Applications. SIAM . McKee, T. A. and McMorris, F. R. 1999. Topics in Intersection Graph Theory. SIAM Monographs on Discrete Mathematics and Applications. SIAM."},{"key":"e_1_2_1_27_1","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier R.","unstructured":"Niedermeier , R. 2006. Invitation to Fixed-Parameter Algorithms . Oxford University Press , Oxford . Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the ACM SIGPLAN Workshop on ML. 77--86","author":"Okasaki C.","unstructured":"Okasaki , C. and Gill , A . 1998. Fast mergeable integer maps . In Proceedings of the ACM SIGPLAN Workshop on ML. 77--86 . Okasaki, C. and Gill, A. 1998. Fast mergeable integer maps. In Proceedings of the ACM SIGPLAN Workshop on ML. 77--86."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/1385-7258(77)90055-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1198\/1061860043515"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 7th Conference on the Theory and Applications of Graphs","author":"Prisner E.","year":"1995","unstructured":"Prisner , E. 1995 . Graphs with few cliques . In Proceedings of the 7th Conference on the Theory and Applications of Graphs . Wiley, New York. 945--956. Prisner, E. 1995. Graphs with few cliques. In Proceedings of the 7th Conference on the Theory and Applications of Graphs. Wiley, New York. 945--956."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/354880.354902"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412228.1412236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:56:30Z","timestamp":1672304190000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1412236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":32,"alternative-id":["10.1145\/1412228.1412236"],"URL":"http:\/\/dx.doi.org\/10.1145\/1412228.1412236","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2009,2]]}}}