Loading...
Please wait, while we are loading the content...
Similar Documents
Exploiting a Hypergraph Model for Finding Golomb Rulers (2014)
| Content Provider | CiteSeerX |
|---|---|
| Author | Sorge, Manuel Moser, Hannes Niedermeier, Rolf Weller, Mathias |
| Abstract | Golomb rulers are special rulers where for any two marks it holds that the distance between them is unique. They find applications in radio frequency selection, radio astronomy, data encryption, 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 consider a natural hypergraph characterization of rulers and investigate the construction and structure of the corresponding hypergraphs. We exploit their properties to derive polynomial-time data reduction rules that reduce a given instance of GSR to an equivalent one with O(k3) marks. Finally, we complement a recent computational complexity study of GSR by providing a simplified reduction that shows NP-hardness even when all integers are bounded by a polynomial in the input length. |
| File Format | |
| Journal | ACTA INFORMATICA |
| Publisher Date | 2014-01-01 |
| Access Restriction | Open |
| Subject Keyword | Hypergraph Model Finding Golomb Ruler Radio Frequency Selection Ruler Golomb Equivalent One Golomb Ruler Important Subproblem Special Ruler Compact Golomb Ruler Communication Network Polynomial-time Data Reduction Rule Recent Computational Complexity Study Data Encryption Simplified Reduction Golomb Subruler Radio Astronomy Natural Hypergraph Characterization Parameterized Complexity Perspective Input Length Corresponding Hypergraphs |
| Content Type | Text |
| Resource Type | Article |
