Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleUniversal Gr\"obner basis associated with the maximum flow problem.
Author(s) Daisuke Ikegami, Sennosuke Watanabe, Yoshihide Watanabe
TypeArticle in Journal
AbstractWe 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 st 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 st directed paths, which yield the generator of the toric ideal associated with the reduced incidence matrix of the digraph.
KeywordsMaximum flow problem, Circuit, Universal Gröbner basis
ISSN0916-7005; 1868-937X/e
URL http://link.springer.com/article/10.1007%2Fs13160-012-0080-2
LanguageEnglish
JournalJapan J. Ind. Appl. Math.
Volume30
Number1
Pages39--50
PublisherSpringer Japan, Tokyo
Year2013
Edition0
Translation No
Refereed No
Webmaster