Edge-disjoint routing in plane switch graphs in linear time.

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

Full beskrivning

Bibliografiska uppgifter

I publikationen:	Journal of the ACM 51, 4 (2004).
Huvudupphovsman:	Hochstein, J.M
Materialtyp:	Artikel
Språk:	English
Ämnen:	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.