Parameterized complexity of superstring problems

DOI10.1007/s00453-016-0193-0zbMath1380.68217arXiv1502.01461OpenAlexW1549494001WikidataQ60488379 ScholiaQ60488379MaRDI QIDQ1679230

Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh, Fedor V. Fomin, Ivan A. Bliznets

Publication date: 9 November 2017

Published in: Algorithmica, Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.01461

zbMATH Keywords

parameterized complexitykernelizationshortest superstring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• On finding minimal length superstrings
• Dynamic programming meets the principle of inclusion and exclusion
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• Parametrized complexity theory.
• Solving 3-Superstring in 3 n/3 Time
• Representative Sets of Product Families
• Algorithms in Computational Molecular Biology
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Fast Pattern Matching in Strings
• Color-coding
• Kernelization Lower Bounds by Cross-Composition
• Parameterized Algorithms
• Maximum matching and a polyhedron with 0,1-vertices
• Lyndon Words and Short Superstrings

This page was built for publication: Parameterized complexity of superstring problems