An extension of the König-Egerváry property to node-weighted bidirected graphs

DOI10.1007/BF01580775zbMath0653.90083OpenAlexW2066441105MaRDI QIDQ1108202

Jean-Marie Bourjolly

Publication date: 1988

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580775

zbMATH Keywords

matchinginteger linear programmingmixed graphsbidirected graphsnode packingconnected, finite, undirected graphKönig- Egerváry propertypolynomial time recognition algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Linear programming (90C05) Boolean programming (90C09)

Related Items

Binary integer programs with two variables per inequality ⋮ A network approach for specially structured linear programs arising in 0-1 quadratic optimization

Cites Work

• \(b\)-matching degree-sequence polyhedra
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Node-weighted graphs having the König-Egerváry property
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• An Efficient Primal Simplex Algorithm for Maximum Weighted Vertex Packing on Bipartite Graphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Unnamed Item
• Unnamed Item