Eisenbrand, Friedrich and Grandoni, Fabrizio (2004) On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326 (1-3). pp. 57-67. ISSN 0304-3975
|
Text
1-s2.0-S030439750400372X-main.pdf - Published Version Download (231kB) | Preview |
Official Website: http://dx.doi.org/10.1016/j.tcs.2004.05.009
Abstract
We provide simple, faster algorithms for the detection of cliques and dominating sets of fixed order. Our algorithms are based on reductions to rectangular matrix multiplication. We also describe an improved algorithm for diamonds detection.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Uncontrolled Keywords: | Parameterized algorithms; Clique; Dominating set; Diamonds detection |
| Subjects: | Computer sciences |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 15:18 |
| Last Modified: | 24 May 2016 06:20 |
| URI: | http://repository.supsi.ch/id/eprint/4535 |
Actions (login required)
 |
View Item |