ISSN:
1432-0541
Keywords:
Graph algorithms
;
Planar graphs
;
Bidirectional edges
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The all-bidirectional-edges problem is to find an edge-labeling of an undirected networkG=(V, E), with a source and a sink, such that an edgee=uv inE is labeled 〈u, v〉 or 〈u, u〉 (or both) depending on the existence of a (simple) path from the source to the sink traversinge, that visits the verticesu andv in the orderu, v orv, u respectively. The best-known algorithm for this problem requiresO(¦V¦·¦E¦) time [5]. We show that the problem is solvable optimally on a planar graph.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01190896
Permalink