✦ LIBER ✦

On the parameterized complexity of short computation and factorization

✍ Scribed by Liming Cai; Jianer Chen; Rodney G. Downey; Michael R. Fellows

Publisher: Springer
Year: 1997
Tongue: English
Weight: 169 KB
Volume: 36
Category: Article
ISSN: 0933-5846
DOI: 10.1007/s001530050069

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the Parameterized Complexity of Layer

On the Parameterized Complexity of Layered Graph Drawing

✍ Vida Dujmović; Michael R. Fellows; Matthew Kitching; Giuseppe Liotta; Catherine 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 537 KB

On the parameterized complexity of the M

On the parameterized complexity of the Multi-MCT and Multi-MCST problems

✍ Wenbin Chen; Matthew C. Schmidt; Nagiza F. Samatova 📂 Article 📅 2009 🏛 Springer US 🌐 English ⚖ 244 KB

The Compatibility of Binary Characters o

The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms

✍ Iyad A. Kanj; Luay Nakhleh; Ge Xia 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 525 KB

On the factorization and parameterizatio

On the factorization and parameterization of scattering information

✍ D.K. Hoffman; C. Chan; D.J. Kouri 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 749 KB

Parameterized Complexity: The Main Ideas

Parameterized Complexity: The Main Ideas and Connections to Practical Computing

✍ Michael R. Fellows 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 359 KB

On the parameterized complexity of the f

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

✍ Krzysztof Pietrzak 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 205 KB

We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W ½1-hard. Unless W ½1 ¼ FPT; this rules out the existence of algorithms with time complexity of Oð f ðkÞn a Þ for those pro