Restricted and swap common superstring: a multivariate algorithmic perspective
DOI10.1007/S00453-014-9882-8zbMATH Open1328.68323DBLPjournals/algorithmica/BonizzoniDMZ15OpenAlexW2045180669WikidataQ57518312 ScholiaQ57518312MaRDI QIDQ494787FDOQ494787
Authors: Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri, Italo Zoppis 
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
Recommendations
- Restricted and swap common superstring: a parameterized view
- Restricted common superstring and restricted common supersequence
- More on the complexity of common superstring and supersequence problems
- Solving 3-superstring in \(3^{n/3}\) time
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Cites Work
- Algorithms on Strings, Trees and Sequences
- Some APX-completeness results for cubic graphs
- On problems without polynomial kernels
- Parametrized complexity theory.
- Color-coding
- \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
- Algorithms – ESA 2004
- Title not available (Why is that?)
- Title not available (Why is that?)
- Infeasibility of instance compression and succinct PCPs for NP
- Efficient special cases of pattern matching with swaps
- Pattern Matching with Swaps
- Kernel bounds for disjoint cycles and disjoint paths
- Cross-composition: a new technique for kernelization lower bounds
- Reflections on multivariate algorithmics and problem parameterization
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- Linear approximation of shortest superstrings
- Title not available (Why is that?)
- Mathematical Foundations of Computer Science 2005
- Restricted common superstring and restricted common supersequence
- Swap and mismatch edit distance
- Restricted and swap common superstring: a parameterized view
Cited In (3)
This page was built for publication: Restricted and swap common superstring: a multivariate algorithmic perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494787)
