Strongly polynomial simplex algorithm for bipartite vertex packing

DOI10.1016/0166-218X(94)00122-TzbMath0848.90116MaRDI QIDQ1917242

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

Programming involving graphs or networks (90C35) Trees (05C05) Linear programming (90C05) 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)

Related Items (1)

A new strongly polynomial dual network simplex algorithm

Cites Work

• Computational experience with a polynomial-time dual simplex algorithm for the transportation problem
• The ellipsoid method and its consequences in combinatorial optimization
• Maximum matchings in bipartite graphs via strong spanning trees
• Efficient dual simplex algorithms for the assignment problem
• 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

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