Arrow Research search

Author name cluster

Karsten Weihe

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
2 author rows

Possible papers

6

FOCS Conference 1999 Conference Paper

Edge-Disjoint Routing in Plane Switch Graphs in Linear Time

  • Karsten Weihe

By a switch graph we mean an undirected graph G=(P/spl cup//spl dot/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 (s/sub 1/, t/sub 1/), .. ., (s/sub k/, t/sub k/) of pairs of plugs, the problem is to find edge-disjoint paths p/sub 1/, .. ., p/sub k/ such that every p/sub i/ connects s/sub i/ with t/sub i/. The best asymptotic worst case complexity known so far is quadratic in the number of vertices. A linear, and thus asymptotically optimal algorithm is introduced. This result may be viewed as a concluding "key-stone" for a number of previous results on various special cases of the problem.

Details

FOCS Conference 1994 Conference Paper

Maximum (s, t)-Flows in Planar Networks in O(|V| log |V|) Time

  • Karsten Weihe

Let G=(V, A) be a directed, planar graph, let s, t /spl isin/ V, s/spl ne/t, and let c/sub a/>0 be the capacity of an arc a/spl isin/A. The problem is to find a maximum flow from s to t in G: subject to these capacities. The fastest algorithm known so far requires /spl Oscr/(|V|/spl middot//sup 3//spl radic/|V|/spl middot/log|V|) time, whereas the algorithm introduced in this paper requires only /spl Oscr/(|V|log|V|) time. >

Details