A simple algorithm that proves half‐integrality of bidirected network programming

DOI10.1002/NET.20117MaRDI QIDQ5487821zbMATH OpenOpenAlexFDO

Authors Ethan D. Bolker, Thomas Zaslavsky

Publication date 12 September 2006

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20117

zbMATH Keywords

bidirected graphhalf-integralityincidence matrixsigned-graph matroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Signed and weighted graphs (05C22) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• A bidirected generalization of network matrices
• On the existence of an integral potential in a weighted bidirected graph
• On matrices with the Edmonds-Johnson property arising from bidirected graphs
• Half-integral vertex covers on bipartite bidirected graphs: total dual integrality and cut-rank
• On the representability of totally unimodular matrices on bidirected graphs

Cites work

• Orientation of signed graphs

Cited in

(12)

• On the representability of totally unimodular matrices on bidirected graphs
• Conformal decomposition of integral flows on signed graphs with outer-edges
• Resolution of indecomposable integral flows on signed graphs
• Recognizing binet matrices
• Conformal decomposition of integral tensions and potentials of signed graphs
• Convergence and Correctness of Max-Product Belief Propagation for Linear Programming
• A bidirected generalization of network matrices
• Matroids of gain signed graphs
• A mathematical programming approach for recognizing binet matrices
• On the foundations of signed graphs. I: Chain groups, frame matroid, and bivariate flow polynomial
• On the existence of an integral potential in a weighted bidirected graph
• The number of nowhere-zero flows on graphs and signed graphs

This page was built for publication: A simple algorithm that proves half‐integrality of bidirected network programming

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