research article
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.
Type
research article
Author(s)
Grandoni, Fabrizio
Date Issued
2004
Published in
Volume
326
Issue
1-3
Start page
57
End page
67
Editorial or Peer reviewed
REVIEWED
Written at
OTHER
EPFL units
Available on Infoscience
May 13, 2008
Use this identifier to reference this record