Algorithmic Aspects of Golomb Ruler Construction

Details Algorithmic Aspects of Golomb Ruler Construction Algorithmic Aspects of Golomb Ruler Construction

2010-05-28

arxiv.org/abs/1005.5395v2

Computer Science

Discrete Mathematics

Scientific paper

We consider Golomb rulers and their construction. Common rulers feature marks at every unit measure, distances can often be measured with numerous pairs of marks. On Golomb rulers, for every distance there are at most two marks measuring it. The construction of optimal---with respect to shortest length for given number of marks or maximum number of marks for given length---is nontrivial, various problems regarding this are NP-complete. We give a simplified hardness proof for one of them. We use a hypergraph characterization of rulers and Golomb rulers to illuminate structural properties. This gives rise to a problem kernel in a fixed-parameter approach to a construction problem. We also take a short look at the practical implications of these considerations.

Affiliated with

Also associated with

No associations

Rating

Algorithmic Aspects of Golomb Ruler Construction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithmic Aspects of Golomb Ruler Construction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic Aspects of Golomb Ruler Construction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-85971