Triangles, 4-Cycles and Parameterized (In-)Tractability

DOI10.1007/11785293_29MaRDI QIDQ5757905zbMATH OpenOpenAlexFDO

Authors Venkatesh Raman, Saket Saurabh

Publication date 7 September 2007

Published in Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11785293_29

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• scientific article; zbMATH DE number 125608
• Parameterized Algorithms for Generalized Domination
• Perfect domination and small cycles
• Dominating set is fixed parameter tractable in claw-free graphs

Cited in

(8)

• Finding a potential community in networks
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• The kernelization complexity of connected domination in graphs with (no) small cycles
• Perfect domination and small cycles
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles

This page was built for publication: Triangles, 4-Cycles and Parameterized (In-)Tractability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5757905)