Strongly polynomial simplex algorithm for bipartite vertex packing

DOI10.1016/0166-218X(94)00122-TMaRDI QIDQ1917242zbMATH OpenFDO

Authors Ronald D. Armstrong, Zhiying Jin

Publication date 7 July 1996

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

bipartite graphnode labelingstrong spanning treesweighted vertex packing

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• scientific article; zbMATH DE number 2159164
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• scientific article; zbMATH DE number 434914

Cites work

• A competitive (dual) simplex method for the assignment problem
• A new approach to the maximum-flow problem
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• An Efficient Primal Simplex Algorithm for Maximum Weighted Vertex Packing on Bipartite Graphs
• Computational experience with a polynomial-time dual simplex algorithm for the transportation problem
• Efficient dual simplex algorithms for the assignment problem
• Maximum matchings in bipartite graphs via strong spanning trees
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(4)

• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• scientific article; zbMATH DE number 2159164 (Why is no real title available?)
• A new strongly polynomial dual network simplex algorithm
• A combinatorial algorithm for weighted stable sets in bipartite graphs

This page was built for publication: Strongly polynomial simplex algorithm for bipartite vertex packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1917242)