The Graham-Knowlton problem revisited

Navin Goyal, Sachin Lodha, S. Muthukrishnan

    Research output: Contribution to journalArticle


    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
    Issue number3
    StatePublished - Jun 2006

    ASJC Scopus subject areas

    • 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

    Goyal, N., Lodha, S., & Muthukrishnan, S. (2006). The Graham-Knowlton problem revisited. Theory of Computing Systems, 39(3), 399-412.