The Graham-Knowlton problem revisited

Navin Goyal, Sachin Lodha, S. Muthukrishnan

    Research output: Contribution to journalArticlepeer-review


    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


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

    Cite this