Call routing and the ratcatcher

P. D. Seymour, R. Thomas

Research output: Contribution to journalArticle

219 Scopus citations

Abstract

Suppose we expect there to be p(ab) phone calls between locations a and b, all choices of a, b from some set L of locations. We wish to design a network to optimally handle these calls. More precisely, a "routing tree" is a tree T with set of leaves L, in which every other vertex has valency 3. It has "congestion" <k if for every edge e of T, there are fewer than k calls which will be routed along e, that is, between location a, b in different components of T/e. Deciding if there is a routing tree with congestion <k is NP-hard, but if the pairs ab, with p(ab)>0 form the edges of a planar graph G, there is an efficient, strongly polynomial algorithm. This is because the problem is equivalent to deciding if a ratcatcher can corner a rat loose in the walls of a house with floor plan G, where p(ab) is a thickness of the wall ab. The ratcatcher carries a noisemaker of power k, and the rat will not move through any wall in which the noise level is too high (determined by the total thickness of the intervening walls between this one and the noisemaker). It follows that branch-width is polynomially computable for planar graphs-that too is NP-hard for general graphs.

Original languageEnglish (US)
Pages (from-to)217-241
Number of pages25
JournalCombinatorica
Volume14
Issue number2
DOIs
StatePublished - Jun 1 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification code (1991): 05C78, 05C85

Fingerprint Dive into the research topics of 'Call routing and the ratcatcher'. Together they form a unique fingerprint.

  • Cite this