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). |
|---|---|
| मुख्य लेखक: | |
| स्वरूप: | लेख |
| भाषा: | English |
| विषय: |