Access Restriction

Author Gramm, Jens ♦ Guo, Jiong ♦ Hffner, Falk ♦ Niedermeier, Rolf
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Clique cover ♦ Data reduction ♦ Fixed-parameter tractability
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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-02-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 13
Page Count 14
Starting Page 2.2
Ending Page 2.15

Open content in new tab

   Open content in new tab
Source: ACM Digital Library