On the complexity of fixed parameter clique and dominating set
type: Item
instance of: scholarly article
title: On the complexity of fixed parameter clique and dominating set
zbMATH Open document ID: 1071.68030
author: Friedrich Eisenbrand
author: Fabrizio Grandoni
published in: Theoretical Computer Science
publication date: 2005-01-11T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 2126106
zbMATH Keywords: Parameterized algorithms
zbMATH Keywords: Clique
zbMATH Keywords: Dominating set
zbMATH Keywords: Diamonds detection
Wikidata QID: Q56210401
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.05.009
OpenAlex ID: W1973113631
cites work: Finding and counting given length cycles
cites work: Q3852212
cites work: Rectangular matrix multiplication revisited
cites work: Matrix multiplication via arithmetic progressions
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Q4393480
cites work: Q5724802
cites work: Algorithms and Data Structures
cites work: Q4198056
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Fast rectangular matrix multiplication and applications
cites work: Finding a Minimum Circuit in a Graph
cites work: On Syntactic versus Computational Views of Approximability
cites work: Finding and counting small induced subgraphs efficiently
cites work: Q3688439
cites work: Q4527015
DOI: 10.1016/J.TCS.2004.05.009
Recommended article: On the parameterized complexity of approximating dominating set
Recommended article: On the Parameterized Complexity of Approximating Dominating Set
Recommended article: On hardness of approximating the parameterized clique problem
Recommended article: Parameterized approximation of dominating set problems
Recommended article: Exact Algorithms for Dominating Clique Problems
Recommended article: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
Recommended article: Q2721971
Recommended article: The parameterized complexity of dominating set and friends revisited for structured graphs
Recommended article: Parameterized complexity of minimum membership dominating set
description: scientific article; zbMATH DE number 2126106