An extension of the könig-egerváry property to node-weighted bidirected graphs

1. B. Aspvall, M.F. Plass and R.E. Tarjan, “A linear-time algorithm for testing the truth of certain quantitative Boolean formulas,”Information Processing Letters 8 (1979) 121–123.

   Google Scholar 

2. J.-M. Bourjolly, “Integral and fractional node-packing, and pseudo-Boolean programming,” Ph.D. Thesis, University of Waterloo, 1986.

3. J.-M. Bourjolly, P.L. Hammer and B. Simeone, “Node-weighted graphs having the König-Egerváry property,”Mathematical Programming Study 22 (1984) 44–63.

   Google Scholar 

4. J. Edmonds and E.L. Johnson, “Matching: A well-solved class of integer linear programs,” in: R. Guy et al., eds.,Combinatorial Structures and their Applciations (Gordon and Breach, New York, 1970; Proceedings of the Calgary Symposium, June 1969).

   Google Scholar 

5. J. Edmonds and R.M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems,”Journal of the Association for Computing Machinery 19 (1972) 248–264.

   Google Scholar 

6. J. Green-Krótki, “Matching polyhedra,” M.Sc. Thesis, Carleton University, 1980.

7. P.L. Hammer, P. Hansen and B. Simeone, “Roof duality, complementation and persistency in quadratic 0–1 optimization,”Mathematical Programming 28 (1984) 121–155.

   Google Scholar 

8. Y. Ikura and G.L. Nemhauser, “An efficient primal simplex algorithm for maximum weighted vertex packing on bipartite graphs,”Annals of Discrete Mathematics 16 (1982) 149–168.

   Google Scholar 

9. J.L. Kennington and R.V. Helgason,Algorithms for Network Programming (Wiley, 1980).

10. A.B. Marsh, III, “Matching algorithms,” Ph.D. Thesis, The Johns Hopkins University, 1979.

Download references