zbMATH — the first resource for mathematics

Exploiting a hypergraph model for finding Golomb rulers. (English) Zbl 1360.68519
Mahjoub, A. Ridha (ed.) et al., Combinatorial optimization. Second international symposium, ISCO 2012, Athens, Greece, April 19-21, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-32146-7/pbk). Lecture Notes in Computer Science 7422, 368-379 (2012).
Summary: Golomb rulers are special rulers where for any two marks it holds that the distance between them is unique. They find applications in positioning of radio channels, radio astronomy, communication networks, and bioinformatics. An important subproblem in constructing “compact” Golomb rulers is Golomb Subruler (GSR), which asks whether it is possible to make a given ruler Golomb by removing at most \(k\) marks. We initiate a study of GSR from a parameterized complexity perspective. In particular, we develop a hypergraph characterization of rulers and consider the construction and structure of the corresponding hypergraphs. We exploit their properties to derive polynomial-time data reduction rules that lead to a problem kernel for GSR with \(O(k ^{3})\) marks. Finally, we provide a simplified NP-hardness construction for GSR.
For the entire collection see [Zbl 1248.90004].

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