The Graham-Knowlton problem revisited

Navin Goyal, Sachin Lodha, S. Muthukrishnan

Research output: Contribution to journalArticlepeer-review

Abstract

In the late 60s 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.

Original languageEnglish (US)
Pages (from-to)399-412
Number of pages14
JournalTheory of Computing Systems
Volume39
Issue number3
DOIs
StatePublished - Jun 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The Graham-Knowlton problem revisited'. Together they form a unique fingerprint.

Cite this