The complexity of irredundant sets parameterized by size

DOI10.1016/S0166-218X(99)00185-7zbMath0948.68133MaRDI QIDQ1971218

Michael R. Fellows, Rodney G. Downey, Venkatesh Raman

Publication date: 22 March 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

irredundant set

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

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

Related Items

Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles, The parameterized complexity of the induced matching problem, Parameterized complexity of finding subgraphs with hereditary properties.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved fixed-parameter algorithm for vertex cover
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The irredundance number and maximum degree of a graph
• Contributions to the theory of domination, independence and irredundance in graphs
• Threshold dominating sets and an improved characterization of \(W[2\)]
• The sequence of upper and lower domination, independence and irredundance numbers of a graph
• Domination and irredundance in cubic graphs
• The parameterized complexity of sequence alignment and consensus
• On the parameterized complexity of short computation and factorization
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Private Neighbor Cube
• Fixed-Parameter Tractability and Completeness I: Basic Results