A fixed-parameter tractable algorithm for matrix domination

DOI10.1016/J.IPL.2002.12.001MaRDI QIDQ2390264zbMATH OpenOpenAlexFDO

Authors Mark Weston

Publication date 21 July 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2002.12.001

zbMATH Keywords

analysis of algorithmscomputational complexitygraph algorithmsparameterized complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 125608
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
• Fixed-Parameter Tractability and Completeness I: Basic Results

Cites work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Edge Dominating Sets in Graphs
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• scientific article; zbMATH DE number 1418354 (Why is no real title available?)
• Vertex cover: Further observations and further improvements

Cited in

(4)

• Maximum matching and kernelization of edge dominating set
• Efficient domination through eigenvalues
• scientific article; zbMATH DE number 2104735 (Why is no real title available?)
• Parameterized Parallel Computing and First-Order Logic

This page was built for publication: A fixed-parameter tractable algorithm for matrix domination

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