The minimum substring cover problem

DOI10.1016/j.ic.2008.06.002zbMath1162.90592OpenAlexW1620365865MaRDI QIDQ958306

Danny Hermelin, Romeo Rizzi, Dror Rawitz, Stéphane Vialette

Publication date: 3 December 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.06.002

zbMATH Keywords

approximation algorithmsrandomized roundingdictionary generationlocal-ratiosubstring cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Some algorithmic results for [2-sumset covers], Efficient Computation of 2-Covers of a String., Effective heuristics for the Set Covering with Pairs Problem, Exact and heuristic approaches for the set cover with pairs problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• A note on decidability questions on presentations of word semigroups
• Some APX-completeness results for cubic graphs
• One for the price of two: a unified approach for approximating covering problems
• Elementariness of a finite set of words is co-NP-complete
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science