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). |
|---|---|
| 主要作者: | |
| 格式: | 文件 |
| 语言: | 英语 |
| 主题: |