Restricted and swap common superstring: a multivariate algorithmic perspective

DOI10.1007/s00453-014-9882-8zbMath1328.68323OpenAlexW2045180669WikidataQ57518312 ScholiaQ57518312MaRDI QIDQ494787

Italo Zoppis, Giancarlo Mauri, Paola Bonizzoni, Riccardo Dondi

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9882-8

zbMATH Keywords

algorithmsparameterized complexityAPX-hardnessstring comparisonshortest common superstring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (1)

Parameterized tractability of the maximum-duo preservation string mapping problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient special cases of pattern matching with swaps
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• On problems without polynomial kernels
• Some APX-completeness results for cubic graphs
• Swap and mismatch edit distance
• Parametrized complexity theory.
• Restricted Common Superstring and Restricted Common Supersequence
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• Algorithms on Strings, Trees and Sequences
• Linear approximation of shortest superstrings
• Color-coding
• Pattern Matching with Swaps
• Restricted and Swap Common Superstring: A Parameterized View
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Algorithms – ESA 2004
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Restricted and swap common superstring: a multivariate algorithmic perspective