Details:
Title  Universal Gr\"obner basis associated with the maximum flow problem.  Author(s)  Daisuke Ikegami, Sennosuke Watanabe, Yoshihide Watanabe  Type  Article in Journal  Abstract  We give a formulation of the maximum flow problem as an integer programming problem in the standard form. We characterize elementary vectors of the kernel lattice of the matrix coefficient in our formulation in terms of the combinatorial property of the graph, such as circuits and s–t paths, and we determine the universal Gröbner basis of the toric ideal associated with the maximum flow problem. Next, we examine the kernel lattice of the reduced incidence matrix of the digraph. Under suitable assumptions for the digraph, we prove that it is generated by all incidence vectors of s–t directed paths, which yield the generator of the toric ideal associated with the reduced incidence matrix of the digraph.  Keywords  Maximum flow problem, Circuit, Universal Gröbner basis  ISSN  09167005; 1868937X/e 
URL 
http://link.springer.com/article/10.1007%2Fs1316001200802 
Language  English  Journal  Japan J. Ind. Appl. Math.  Volume  30  Number  1  Pages  3950  Publisher  Springer Japan, Tokyo  Year  2013  Edition  0  Translation 
No  Refereed 
No 
