On matrices with the Edmonds-Johnson property arising from bidirected graphs
From MaRDI portal
Publication:1745732
DOI10.1016/j.jctb.2017.09.013zbMath1384.05107WikidataQ57568032 ScholiaQ57568032MaRDI QIDQ1745732
Alberto Del Pia, Giacomo Zambelli, Antoine Musitelli
Publication date: 18 April 2018
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2017.09.013
integer programming; combinatorial optimization; excluded minors; bidirected graphs; Edmonds-Johnson property; strong Chvàtal rank
90C10: Integer programming
90C27: Combinatorial optimization
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(k\)-integrality, an extension of total unimodularity
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Matrices with the Edmonds-Johnson property
- Rational and integral \(k\)-regular matrices.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Optimization with binet matrices
- Edmonds polytopes and a hierarchy of combinatorial problems
- Network Formulations of Mixed-Integer Programs
- Half-Integral Vertex Covers on Bipartite Bidirected Graphs: Total Dual Integrality and Cut-Rank
- The traveling salesman problem on a graph and some related integer polyhedra
- Sensitivity theorems in integer linear programming
- On Cutting Planes
- Matching, Euler tours and the Chinese postman
- Mixed-Integer Vertex Covers on Bipartite Graphs