On the complexity of fixed parameter clique and dominating set

DOI10.1016/j.tcs.2004.05.009zbMath1071.68030WikidataQ56210401 ScholiaQ56210401MaRDI QIDQ703534

Fabrizio Grandoni, Friedrich Eisenbrand

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.05.009

zbMATH Keywords

Dominating set; Clique; Diamonds detection; Parameterized algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Open problems around exact algorithms, The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics

Cites Work

• Finding and counting small induced subgraphs efficiently
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Finding and counting given length cycles
• Matrix multiplication via arithmetic progressions
• Fast rectangular matrix multiplication and applications
• Rectangular matrix multiplication revisited
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Finding a Minimum Circuit in a Graph
• On Syntactic versus Computational Views of Approximability
• Algorithms and Data Structures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item