Multi-Terminal Network Flows 论文

摘要

Previous article Next article Multi-Terminal Network FlowsR. E. Gomory and T. C. HuR. E. Gomory and T. C. Huhttps://doi.org/10.1137/0109047PDFPDF PLUSBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] L. R. Ford, Jr. and , D. R. Fulkerson, Maximal flow through a network, Canad. J. Math., 8 (1956), 399–404 MR0079251 0073.40203 CrossrefGoogle Scholar[2] Wataru Mayeda, Terminal and branch capacity matrices of a communication net, IRE Trans., CT-7 (1960), 261–269 MR0120055 Google Scholar[3] R. T. Chien, Synthesis of a communication net, IBM J. Res. Develop., 4 (1960), 311–320 MR0122574 0095.11404 CrossrefISIGoogle Scholar[4] Joseph B. Kruskal, Jr., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc., 7 (1956), 48–50 MR0078686 0070.18404 CrossrefGoogle Scholar[5] R. C. Prim, Shortest connection networks and some generalizations, Bell System Tech. J., 36 (1957), 1389–1401 CrossrefISIGoogle Scholar[6] R. E. Gomory and , T. C. Hu, An application of generalized linear programming to network flows, IBM Research Report RC-319, 1960, September Google Scholar[7] Claude Berge, Théorie des graphes et ses applications, Collection Universitaire de Mathématiques, II, Dunod, Paris, 1958viii+277 MR0102822 Google Scholar[8] O. Wing, Minimal realization of a communication net under uniform cost, IBM Research Report ES 0026, 1960, August Google Scholar Previous article Next article FiguresRelatedReferencesCited ByDetails When Do Gomory--Hu Subtrees Exist?Guyslain Naves and Bruce ShepherdSIAM Journal on Discrete Mathematics, Vol. 36, No. 3 | 5 July 2022AbstractPDF (539 KB)Local Flow Partitioning for Faster Edge ConnectivityMonika Henzinger, Satish Rao, and Di WangSIAM Journal on Computing, Vol. 49, No. 1 | 7 January 2020AbstractPDF (586 KB)Efficiently Realizing Interval SequencesAmotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror RawitzSIAM Journal on Discrete Mathematics, Vol. 34, No. 4 | 9 November 2020AbstractPDF (530 KB)Densities, Matchings, and Fractional Edge-ColoringsXujin Chen, Wenan Zang, and Qiulan ZhaoSIAM Journal on Optimization, Vol. 29, No. 1 | 22 January 2019AbstractPDF (504 KB)Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest PathsHung-Chun Liang and Hsueh-I LuSIAM Journal on Discrete Mathematics, Vol. 31, No. 1 | 7 March 2017AbstractPDF (826 KB)Fast Augmenting Paths by Random Sampling from Residual GraphsSIAM Journal on Computing, Vol. 44, No. 2 | 31 March 2015AbstractPDF (328 KB)Preserving Terminal Distances Using MinorsSIAM Journal on Discrete Mathematics, Vol. 28, No. 1 | 28 January 2014AbstractPDF (315 KB)Computing the Girth of a Planar Graph in Linear TimeSIAM Journal on Computing, Vol. 42, No. 3 | 30 May 2013AbstractPDF (431 KB)Efficient Edge Splitting-Off Algorithms Maintaining All-Pairs Edge-ConnectivitiesSIAM Journal on Computing, Vol. 42, No. 3 | 20 June 2013AbstractPDF (344 KB)Integer Exact Network Synthesis ProblemSIAM Journal on Discrete Mathematics, Vol. 23, No. 1 | 14 November 2008AbstractPDF (275 KB)Odd Minimum Cut Sets and b-Matchings RevisitedSIAM Journal on Discrete Mathematics, Vol. 22, No. 4 | 1 October 2008AbstractPDF (149 KB)Fractional Packing of T-JoinsSIAM Journal on Discrete Mathematics, Vol. 17, No. 4 | 1 August 2006AbstractPDF (149 KB)Compact Representations of CutsSIAM Journal on Discrete Mathematics, Vol. 14, No. 1 | 1 August 2006AbstractPDF (197 KB)The General Structure of Edge-Connectivity of a Vertex Subset in a Graph and its Incremental Maintenance. Odd CaseSIAM Journal on Computing, Vol. 30, No. 3 | 27 July 2006AbstractPDF (547 KB)An 8-Approximation Algorithm for the Subset Feedback Vertex Set ProblemSIAM Journal on Computing, Vol. 30, No. 4 | 27 July 2006AbstractPDF (257 KB)A Fast Algorithm for Optimally Increasing the Edge ConnectivitySIAM Journal on Computing, Vol. 26, No. 4 | 28 July 2006AbstractPDF (455 KB)Network Design Using Cut InequalitiesSIAM Journal on Optimization, Vol. 6, No. 3 | 12 July 2006AbstractPDF (1568 KB)When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on NetworksSIAM Journal on Computing, Vol. 24, No. 3 | 13 July 2006AbstractPDF (2239 KB)Counterexamples for Directed and Node Capacitated Cut-TreesSIAM Journal on Computing, Vol. 24, No. 3 | 13 July 2006AbstractPDF (752 KB)Finding k Cuts within Twice the OptimalSIAM Journal on Computing, Vol. 24, No. 1 | 31 July 2006AbstractPDF (1011 KB)The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar GraphsSIAM Journal on Discrete Mathematics, Vol. 7, No. 3 | 17 February 2012AbstractPDF (2256 KB)Finding the Hidden Path: Time Bounds for All-Pairs Shortest PathsSIAM Journal on Computing, Vol. 22, No. 6 | 31 July 2006AbstractPDF (2505 KB)Computing Edge-Connectivity in Multigraphs and Capacitated GraphsSIAM Journal on Discrete Mathematics, Vol. 5, No. 1 | 8 August 2006AbstractPDF (1231 KB)Augmenting Graphs to Meet Edge-Connectivity RequirementsSIAM Journal on Discrete Mathematics, Vol. 5, No. 1 | 8 August 2006AbstractPDF (3861 KB)Integer Polyhedra Arising from Certain Network Design Problems with Connectivity ConstraintsSIAM Journal on Discrete Mathematics, Vol. 3, No. 4 | 8 August 2006AbstractPDF (2792 KB)Very Simple Methods for All Pairs Network Flow AnalysisSIAM Journal on Computing, Vol. 19, No. 1 | 31 July 2006AbstractPDF (1671 KB)A Graph Theoretic Approach to Statistical Data SecuritySIAM Journal on Computing, Vol. 17, No. 3 | 13 July 2006AbstractPDF (2539 KB)Optimum Communication Spanning Trees in Series-Parallel NetworksSIAM Journal on Computing, Vol. 14, No. 4 | 13 July 2006AbstractPDF (1150 KB)Constrained Optimum Communication Trees and Sensitivity AnalysisSIAM Journal on Computing, Vol. 13, No. 2 | 13 July 2006AbstractPDF (1157 KB)Simple Constructions for Multiterminal Network Flow SynthesisSIAM Journal on Computing, Vol. 12, No. 1 | 31 July 2006AbstractPDF (1076 KB)A Multiterminal Minimum Cut Algorithm for Planar GraphsSIAM Journal on Computing, Vol. 9, No. 2 | 13 July 2006AbstractPDF (624 KB)Multi-Terminal 0–1 FlowSIAM Journal on Computing, Vol. 8, No. 3 | 13 July 2006AbstractPDF (745 KB)Bottlenecks and Edge Connectivity in Unsymmetrical NetworksSIAM Journal on Computing, Vol. 8, No. 2 | 13 July 2006AbstractPDF (1090 KB)The Optimal Partitioning of GraphsNicos Christofides and P. BrookerSIAM Journal on Applied Mathematics, Vol. 30, No. 1 | 12 July 2006AbstractPDF (1463 KB)Network Flow and Testing Graph ConnectivitySIAM Journal on Computing, Vol. 4, No. 4 | 13 July 2006AbstractPDF (1277 KB)Optimum Communication Spanning TreesSIAM Journal on Computing, Vol. 3, No. 3 | 13 July 2006AbstractPDF (655 KB)Optimal Linear OrderingD. Adolphson and T. C. HuSIAM Journal on Applied Mathematics, Vol. 25, No. 3 | 28 July 2006AbstractPDF (1738 KB)k-Components, Clusters and Slicings in GraphsDavid W. MatulaSIAM Journal on Applied Mathematics, Vol. 22, No. 3 | 12 July 2006AbstractPDF (2191 KB)Recent Advances in Network FlowsSIAM Review, Vol. 10, No. 3 | 18 July 2006AbstractPDF (775 KB)On Flows in Pseudosymmetric NetworksRam Prakash GuptaSIAM Journal on Applied Mathematics, Vol. 14, No. 2 | 13 July 2006AbstractPDF (1092 KB)Synthesis of a Communication NetworkR. E. Gomory and T. C. HuJournal of the Society for Industrial and Applied Mathematics, Vol. 12, No. 2 | 28 July 2006AbstractPDF (1705 KB)An Application of Generalized Linear Programming to Network FlowsR. E. Gomory and T. C. HuJournal of the Society for Industrial and Applied Mathematics, Vol. 10, No. 2 | 13 July 2006AbstractPDF (1856 KB) Volume 9, Issue 4| 1961Journal of the Society for Industrial and Applied Mathematics History Submitted:18 November 1960Published online:10 July 2006 InformationCopyright © 1961 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0109047Article page range:pp. 551-570ISSN (print):0368-4245ISSN (online):2168-3484Publisher:Society for Industrial and Applied Mathematics