On parameterized complexity of the multi-MCS problem

DOI10.1016/j.tcs.2008.12.060zbMath1168.68018OpenAlexW2079592951MaRDI QIDQ1019178

Matthew C. Schmidt, Wenbin Chen, 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

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

Cites Work

• Unnamed Item
• Unnamed Item
• The parameterized complexity of sequence alignment and consensus
• Describing parameterized complexity classes
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• On the approximability of the maximum common subgraph problem

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