Exploiting a Hypergraph Model for Finding Golomb Rulers

DOI10.1007/978-3-642-32147-4_33MaRDI QIDQ3167640zbMATH OpenOpenAlexFDO

Authors Manuel Sorge, Hannes Moser, Rolf Niedermeier, Mathias Weller

Publication date 2 November 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32147-4_33

zbMATH Keywords

data reductionNP-hardnessparameterized complexityhitting setproblem kernelforbidden subgraph characterization

Mathematics Subject Classification ID

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

Recommendations

• Exploiting a hypergraph model for finding Golomb rulers
• On the complexity of constructing Golomb rulers
• Local search-based hybrid algorithms for finding Golomb rulers
• Constraint-based local search for Golomb rulers
• An Algorithmic Version of the Hypergraph Regularity Method
• A conjecture on a continuous optimization model for the Golomb ruler problem
• Finding models through graph saturation
• A computational comparison of optimization methods for the Golomb ruler problem
• The hypergraph regularity method and its applications
• scientific article; zbMATH DE number 1161354

Cited in

(5)

• There Are No New Homometric Golomb Ruler Pairs with 12 Marks or Less
• Exploiting a hypergraph model for finding Golomb rulers
• Towards optimal and expressive kernelization for \(d\)-hitting set
• On the complexity of constructing Golomb rulers
• A conjecture on a continuous optimization model for the Golomb ruler problem

This page was built for publication: Exploiting a Hypergraph Model for Finding Golomb Rulers

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