Exploiting a hypergraph model for finding Golomb rulers

DOI10.1007/s00236-014-0202-1zbMath1360.68520OpenAlexW2165271014MaRDI QIDQ471187

Manuel Sorge, Hannes Moser, Mathias Weller, Rolf Niedermeier

Publication date: 14 November 2014

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-014-0202-1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Longest common subsequence problem for unoriented and cyclic strings
• A kernelization algorithm for \(d\)-hitting set
• On the complexity of constructing Golomb rulers
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Fixed-parameter tractability results for feedback set problems in tournaments
• A review of the available construction methods for Golomb rulers
• Local search-based hybrid algorithms for finding Golomb rulers
• Parametrized complexity theory.
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Kernelization – Preprocessing with a Guarantee
• Towards Optimal and Expressive Kernelization for d-Hitting Set
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Exploiting a Hypergraph Model for Finding Golomb Rulers
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• The Algorithmic Aspects of Uncrowded Hypergraphs
• A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler

This page was built for publication: Exploiting a hypergraph model for finding Golomb rulers