Harold N. Gabow
ABSTRACT
Efficient algorithms are given for the bidirected network flow problem and the degree-constrained subgraph problem. Four versions of each are solved, depending on whether edge capacities/multiplicities are one or arbitrary, and whether maximum value/maximum cardinality or minimum cost/maximum weight is the objective. A version of the shortest path problem is also efficiently solved. The algorithms use a reduction technique that solves one problem instance by reducing to a number of problems.
- 1.R.P. Anstee, "An algorithmic proof of Tutte's f-factor theorem", Res. Rept. CORR 81-28, Dept. of Combinatorics and Optimization, Univ. of Waterloo, Waterloo, Ontario, 1981.Google Scholar
- 2.C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973. Google ScholarDigital Library
- 3.R. Bernstein, "Shortest paths in undirected graphs", M.S. Thesis, Stevens Inst. Technology, 1982.Google Scholar
- 4.G.B. Dantzig, Linear Programming and Extensions, Princeton Univ. Press, Princeton, NJ, 1963.Google Scholar
- 5.Edmonds, J., "Maximum matching and a polyhedron with 0,1-vertices," J. Res. Nat. Bur. Standards 69B (1965), 125-130.Google ScholarCross Ref
- 6.J. Edmonds, "An introduction to matching," Notes of Engineering Summer Conference, Univ. of Michigan, Ann Arbor, 1967.Google Scholar
- 7.J. Edmonds and E.L. Johnson, "Matching: A well-solved class of integer linear programs," Proc. Calgray Int. Conf. on Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970, pp. 89-92.Google Scholar
- 8.J. Edmonds and E.L. Johnson, "Matching, Euler tours and the Chinese postman," Math. Programming 5, 1973, pp. 88-124.Google ScholarDigital Library
- 9.J. Edmonds and R.M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems," J. ACM 19, 2, 1972, pp. 248-264. Google ScholarDigital Library
- 10.S. Even and R.E. Tarjan, "Network flow and testing graph connectivity", SIAM J, Comput. 4, 4, 1975, pp. 507-518.Google ScholarDigital Library
- 11.H. Gabow, "An efficient reduction technique for degree-constrained subgraph and bidirectied network flow problems," Tech. Rept. CU-CS-243-83, University of Colorado, Boulder, Colorado, 1983.Google Scholar
- 12.H. Gabow, "An efficient implementation of Edmonds' algorithm for maximum weight matching on graphs," Tech. Rept. CU-CS-075-75, University of Colorado, Boulder, Colorado, 1975.Google Scholar
- 13.A.J. Goldman, "Optimal matchings and degree-constrained subgraphs," J. Res. National Bureau of Standards 68B, 1, 1964, pp. 27-29.Google Scholar
- 14.Z. Galil, S. Micali, H. Gabow, "Priority queues with variable priority and an O(E V log V) algorithm for finding a maximal weighted matching in general graphs," Proc. 23rd Annual Symp. on Foundation of Comp. Sci., 1982, pp. 225-261.Google ScholarCross Ref
- 15.H.N. Gabow and M. Stallman, "Scheduling multitask jobs with deadlines on one processor," abstract.Google Scholar
- 16.Hopcroft, J. and Karp, R, "An n5/2 algorithm for maximum matchings in bipartite graphs," SIAM. J. Comp. 2, 4, 1973, pp. 225-231.Google Scholar
- 17.E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.Google Scholar
- 18.S. Micali and V.V. Vazirani, "An 0((@@@@)V.E) algorithm for finding maximum matching in general graphs," Proc. 21st Annual Symp. on Found. of Comp. Sci., 1980, pp. 17-27.Google Scholar
- 19.Y. Shiloach, "Another look at the degree constrained subgraph problem," Inf. Proc. Letters 12, 2, 1981, pp. 89-92.Google ScholarCross Ref
- 20.D.D.K. Sleator, "An 0(nm log n) algorithm for maximum network flow," Ph.D. Diss., Tech. Rept. STAN-CS-80-831, Stanford Univ., Stanford, CA, 1980. Google ScholarDigital Library
- 21.D. Sleator and R.E. Tarjan, "A data structure for dynamic trees," Proc. 13th Annual ACM Symp. on Th. of Computing, Milwaukee, Wisc., 1981, pp. 114-122. Google ScholarDigital Library
- 22.R.E. Tarjan, "Shortest paths," Ch. 17 in unpublished manuscript. 1982.Google Scholar
- 23.R.J. Urquhart, "Degree-constrained subgraphs of linear graphs," Ph.D. Diss., University of Michigan, 1967.Google Scholar
- 24.L.J. White, "A parametric study of matchings and covering in weighted graphs," Ph.D. Diss., Systems Eng. Lab., Dept. of Electrical Eng., University of Michigan. Ann Arbor, 1967.Google Scholar
Index Terms
- An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems
Recommendations
On the approximability of some degree-constrained subgraph problems
In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph G=(V,E). Let d>=2 be a fixed integer. The Maximumd-degree-bounded ...
On flows in bidirected graphs
Bouchet conjectured that every bidirected graph which admits a nowhere-zero bidirected flow will admit a nowhere-zero bidirected 6-flow [A. Bouchet, Nowhere-zero integer flows on a bidirected graph, J. Combin. Theory Ser. B 34 (1983) 279-292]. He proved ...
Some degree and forbidden subgraph conditions for a graph to have a k -contractible edge
An edge in a k -connected graph is said to be k -contractible if the contraction of the edge results in a k -connected graph. We say that a k -connected graph G satisfies " m -degree-sum condition" if x V ( W ) deg G ( x ) m k + 1 hold for any connected ...
Comments