On the complexity of fixed parameter clique and dominating set

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. © 2004 Elsevier B.V. All rights reserved.


Published in:
Theoretical Computer Science, 326, 1-3, 57 - 67
Year:
2004
Laboratories:




 Record created 2008-05-13, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)