|
In late $60$'s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the fewest trips. We revisit this problem and study its variants and generalizations; we provide a combinatorial characterization of the solution(s) in terms of an associated hypergraph and obtain nearly tight bounds on the minimum number of trips, thereby pleasing electricians. Keywords: Combinatorial structures, combinatorial algorithms, group testing.
|