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),...
| Опубликовано в:: | Journal of the ACM 51, 4 (2004). |
|---|---|
| Главный автор: | |
| Формат: | Статья |
| Язык: | английский |
| Предметы: |