Cited By
View all- Bentz C(2009)Disjoint paths in sparse graphsDiscrete Applied Mathematics10.1016/j.dam.2009.03.009157:17(3558-3568)Online publication date: 1-Oct-2009
A fast algorithm for maximum integral two-commodity flow in planar graphs
Pages 77 - 83
Abstract
We consider in this note the maximum integral two-commodity flow problem in augmented planar graphs, that is with both source sink edges added. We provide an O(nlogn) simple algorithm for finding a maximum integral two-commodity flow in augmented planar graphs.
References
[1]
F. Barahoma, Planar multicommodity flow, max cut, and the Chinese post-man problem, Tech. Rept. 87454-OR (1987).
[2]
J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Elsevier, New York, 1976.
[3]
K.S. Booth, G.S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13 (1976) 335-379.
[4]
S.V. Even, A. Itai, A. Shamir, On the complexity of the timetable and multicommodity flow problem, SIAM J. Comput., 5 (1976) 88-124.
[5]
A. Frank, Packing paths, circuits and cuts¿a survey, Tech. Rept. 88532-OR (1988).
[6]
G.N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Comput., 16 (1987) 1004-1022.
[7]
T.C. Hu, Multi-commodity network flows, Oper. Res., 11 (1963) 334-360.
[8]
E. Korach, Packing of T-cuts, and other aspects of dual integrality, in: Ph.D. thesis, University of Waterloo, Waterloo, Ont, 1982.
[9]
E. Korach, M. Penn, Tight integral duality gap in the Chinese postman problem, in: Tech. Rept. 360, Department of Computer Science, Technion, Haifa, 1985.
[10]
M.V. Lomonosov, On the planar integer two-flow problem, Combinatorica, 3 (1983) 207-218.
[11]
Mei Gu Guan, Graphic programming using odd or even points, Chinese Math., 1 (1962) 273-277.
[12]
M. Middendorf, F. Pfeiffer, On the complexity of the disjoint path problem, Tech. Rept. 89585-OR (1989).
[13]
A. Sebo, Integer plane multicommodity flows with a bounded number of demands, Tech. Rept. 885340-OR (1988).
[14]
P.D. Seymour, On odd cuts and plane multicommodity flow, Proc. London Math. Soc., 42 (1981) 178-192.
Index Terms
- A fast algorithm for maximum integral two-commodity flow in planar graphs
Recommendations
Total domination in planar graphs of diameter two
MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. ...
Largest planar graphs and largest maximal planar graphs of diameter two
Selected papers of the international symposium on applied mathematics, August 2000, Dalian, ChinaLet fk(Δ) be the maximum number of vertices in a planar graph with diameter k and maximum degree Δ. Let gk(Δ) be the maximum number of vertices in a maximal planar graph with diameter k and maximum degree Δ. Seyffarth has shown that g2=⌊3Δ/2+1⌋ for Δ ≥ ...
On maximum planar induced subgraphs
Special issue: Traces of the Latin American conference on combinatorics, graphs and applications: a selection of papers from LACGA 2004, Santiago, ChileThe nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G'. In this case G' is said to be a maximum planar induced subgraph of G. We ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 16 November 1993
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 29 Nov 2024
Other Metrics
Citations
Cited By
View all- Bentz C(2009)Disjoint paths in sparse graphsDiscrete Applied Mathematics10.1016/j.dam.2009.03.009157:17(3558-3568)Online publication date: 1-Oct-2009
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in