The complexity of minimum difference cover

DOI10.1016/J.JDA.2005.03.004MaRDI QIDQ2458927zbMATH OpenOpenAlexFDO

Authors Carlo Mereghetti, Beatrice Palano

Publication date 5 November 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2005.03.004

zbMATH Keywords

NP-completenessdifference coverpseudo-polynomial time

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The complexity of the minimum \(k\)-cover problem
• Complexity and approximability of minimum path-collection exact covers
• On the differential approximation of MIN SET COVER
• On the Complexity of Finding a Minimum Cycle Cover of a Graph
• Computing the minimal covering set
• scientific article; zbMATH DE number 1855660
• On the hardness of approximating minimum vertex cover
• Old and new algorithms for minimal coverability sets

Cites work

• scientific article; zbMATH DE number 3902654 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1342086 (Why is no real title available?)
• scientific article; zbMATH DE number 2209734 (Why is no real title available?)
• A Note on Restricted Difference Bases
• A class of binary recurrent codes with limited error propagation
• Fast lightweight suffix array construction and checking
• GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• Quorums from difference covers
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The chords' problem

Cited in

(8)

• Minimum constellation covers: hardness, approximability and polynomial cases
• Complexity of extremal set decision problem
• Computing runs on a general alphabet
• On the complexity of constructing Golomb rulers
• Covering a set with arithmetic progressions is NP-complete
• scientific article; zbMATH DE number 1855660 (Why is no real title available?)
• Quantum finite automata: advances on Bertoni's ideas
• An algorithm for the difference between set covers

This page was built for publication: The complexity of minimum difference cover

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