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.


Publié dans:
Theoretical Computer Science, 326, 1-3, 57 - 67
Année
2004
Laboratoires:




 Notice créée le 2008-05-13, modifiée le 2018-12-03


Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)