Approximation and fixed parameter algorithms for the approximate cover problem

DOI10.1007/978-3-031-43980-3_7MaRDI QIDQ6545414

Raluca Uricaru, Mathieu Raffinot, Guillaume Blin, Alexandru Popa

Publication date: 29 May 2024

zbMATH Keywords

approximation algorithmNP-hardnessFPT algorithmapproximate cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Enhanced string covering
• Fast algorithm for partial covers in words
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• An on-line string superprimitivity test
• Testing string superprimitivity in parallel
• An optimal algorithm to compute all the covers of a string
• Finding approximate repetitions under Hamming distance.
• Almost periodic sequences.
• Covering problems for partial words and for indeterminate strings
• Covering a string
• Approximate cover of strings
• Computing the \(\lambda \)-covers of a string
• Can we recover the cover?
• Periodicity transforms.
• A Linear-Time Algorithm for Seeds Computation
• Quasi-Periodicity Under Mismatch Errors
• Computing the λ-Seeds of a String
• Computing the cover array in linear time

This page was built for publication: Approximation and fixed parameter algorithms for the approximate cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6545414)