The Graham-Knowlton problem revisited

Navin Goyal; Sachin Lodha; S. Muthukrishnan

doi:10.1007/s00224-005-1242-2

The Graham-Knowlton problem revisited

Navin Goyal, Sachin Lodha, S. Muthukrishnan

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	399-412
Number of pages	14
Journal	Theory of Computing Systems
Volume	39
Issue number	3
DOIs	https://doi.org/10.1007/s00224-005-1242-2
State	Published - Jun 2006

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

Access to Document

10.1007/s00224-005-1242-2

Cite this

@article{ead16ae7fb6b47e6acf210716f36c150,

title = "The Graham-Knowlton problem revisited",

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.",

author = "Navin Goyal and Sachin Lodha and S. Muthukrishnan",

note = "Funding Information: ∗ A preliminary version of this paper appeared in the Proceedings of the 3rd International Conference on Fun with Algorithms, 2004. Navin Goyal was supported in part by NSF Grants CCR-9988526 and NSF Career 0315147.",

year = "2006",

month = jun,

doi = "10.1007/s00224-005-1242-2",

language = "English (US)",

volume = "39",

pages = "399--412",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - The Graham-Knowlton problem revisited

AU - Goyal, Navin

AU - Lodha, Sachin

AU - Muthukrishnan, S.

N1 - Funding Information: ∗ A preliminary version of this paper appeared in the Proceedings of the 3rd International Conference on Fun with Algorithms, 2004. Navin Goyal was supported in part by NSF Grants CCR-9988526 and NSF Career 0315147.

PY - 2006/6

Y1 - 2006/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33646468969&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646468969&partnerID=8YFLogxK

U2 - 10.1007/s00224-005-1242-2

DO - 10.1007/s00224-005-1242-2

M3 - Article

AN - SCOPUS:33646468969

SN - 1432-4350

VL - 39

SP - 399

EP - 412

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 3

ER -

The Graham-Knowlton problem revisited

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this