The complexity of minimum difference cover

DOI10.1016/j.jda.2005.03.004zbMath1134.05084OpenAlexW2054066857MaRDI QIDQ2458927

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

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

Related Items (3)

Computing runs on a general alphabet ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ On the complexity of constructing Golomb rulers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quorums from difference covers
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The chords' problem
• Fast Lightweight Suffix Array Construction and Checking
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• A class of binary recurrent codes with limited error propagation
• GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
• A Note on Restricted Difference Bases

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