
doi: 10.1007/bf01553903
This paper gives efficient algorithms for two classes \(C_{12}\) and \(C_{01}\) of planar undirected graphs. Every graph in \(C_{12}\) has two face boundaries \(B_ 1\) and \(B_ 2\) such that each of the source-sink pairs lies on \(B_ 1\) or \(B_ 2\). On the other hand, every graph in \(C_{01}\) has a face boundary \(B_ 1\) such that some of the source-sink pairs lie on \(B_ 1\) and all the other pairs share a common sink laying on \(B_ 1\). The algorithms run in \(O(kn+nT(n))\) time if a graph has n vertices and k source-sink pairs and T(n) is the time required for finding the single-source shortest paths in a planar graph of n vertices.
shortest path, Analysis of algorithms and problem complexity, Deterministic network models in operations research, cut condition, source-sink pairs, Programming involving graphs or networks, planar undirected graphs
shortest path, Analysis of algorithms and problem complexity, Deterministic network models in operations research, cut condition, source-sink pairs, Programming involving graphs or networks, planar undirected graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
