On parameterized complexity of the multi-MCS problem

DOI10.1016/J.TCS.2008.12.060MaRDI QIDQ1019178zbMATH OpenOpenAlexFDO

Authors Wenbin Chen, Matthew C. Schmidt, Nagiza F. Samatova

Publication date 28 May 2009

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

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

zbMATH Keywords

algorithmsparameterized complexitymaximum common subgraphlinear FPT reduction

Mathematics Subject Classification ID

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

Recommendations

• On the parameterized complexity of the multi-MCT and multi-MCST problems
• On the average-case complexity of MCSP and its variants
• On the parameterized complexity of multiple-interval graph problems
• Complexity and approximability of parameterized MAX-CSPs
• Complexity and Approximability of Parameterized MAX-CSPs
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• scientific article; zbMATH DE number 1748022
• The Parameterized Complexity of Maximality and Minimality Problems
• The parameterized complexity of maximality and minimality problems

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Describing parameterized complexity classes
• On the approximability of the maximum common subgraph problem
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• The parameterized complexity of sequence alignment and consensus

Cited in

(6)

• On the parameterized complexity of the multi-MCT and multi-MCST problems
• MCS Extraction with Sublinear Oracle Queries
• Finding common structured patterns in linear graphs
• scientific article; zbMATH DE number 7650382 (Why is no real title available?)
• Maximum common induced subgraph parameterized by vertex cover
• On the complexity of MMSNP

This page was built for publication: On parameterized complexity of the multi-MCS problem

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