Access Restriction

Author Hochstein, Jan M. ♦ Weihe, Karsten
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2004
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Planar graphs ♦ Edge-disjoint paths
Abstract By a switch graph, we mean an undirected graph $\textit{G}$ = $(\textit{P}$ ⊍ $\textit{W},$ $\textit{E})$ such that all vertices in $\textit{P}$ (the $\textit{plugs})$ have degree one and all vertices in $\textit{W}$ (the $\textit{switches})$ have even degrees. We call $\textit{G}$ $\textit{plane}$ if $\textit{G}$ is planar and can be embedded such that all plugs are in the outer face. Given a set $(s_{1},$ $t_{1}),$ $…,(s_{k},$ $t_{k})$ of pairs of plugs, the problem is to find edge-disjoint paths $p_{1},$ …, $p_{k}$ such that every $p_{i}$ connects $s_{i}$ with $t_{i}.$ The best asymptotic worst-case complexity known so far is quadratic in the number of vertices. In this article, a linear, and thus asymptotically optimal, algorithm is introduced. This result may be viewed as a concluding "keystone" for a number of previous results on various special cases of the problem.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2004-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 51
Issue Number 4
Page Count 35
Starting Page 636
Ending Page 670

Open content in new tab

   Open content in new tab
Source: ACM Digital Library