The complexity of irredundant sets parameterized by size
From MaRDI portal
Publication:1971218
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)
68R10: Graph theory (including graph drawing) in computer science
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack, Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy, 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., Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
