On the complexity of fixed parameter clique and dominating set
2004
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. © 2004 Elsevier B.V. All rights reserved.
Details
Title
On the complexity of fixed parameter clique and dominating set
Author(s)
Eisenbrand, Friedrich ; Grandoni, Fabrizio
Published in
Theoretical Computer Science
Volume
326
Issue
1-3
Pages
57-67
Date
2004
Laboratories
DISOPT
Record Appears in
Scientific production and competences > SB - School of Basic Sciences > MATH - Institute of Mathematics > DISOPT - Chair of Discrete Optimization
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work outside EPFL
Journal Articles
Published
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work outside EPFL
Journal Articles
Published
Record creation date
2008-05-13