00000cab a22000003a 4500 UP-99796217608727395 Buklod 20231007234725.0 m |o d | ta 090225s xx d | ||r ||||| || (iLib)UPD-00075999439 DENGII eng Hochstein, J.M. Edge-disjoint routing in plane switch graphs in linear time. pp. 636-670 By a switch graph, we mean an undirected graph G = (P ⊍ W, E) such that all vertices in P (the plugs) have degree one and all vertices in W (the switches) have even degrees. We call G plane if G is planar and can be embedded such that all plugs are in the outer face. Given a set (s1, t1), ?,(sk, tk) of pairs of plugs, the problem is to find edge-disjoint paths p1, ?, pk such that every pi connects si with ti. 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. Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Routing and layout. Mathematics of computing. Discrete mathematics. Graph theory. Algorithms. Theory. Journal of the ACM 51, 4 (2004). FO UPD DENG-II Article