Sharifov, FirdovsiKutucu, Hakan2024-09-292024-09-2920181304-72051304-7191https://hdl.handle.net/20.500.14619/8570In the paper, we consider a linear programming problem with con-straint matrices whose rows are 0, 1 characteristics vectors of fundamental cuts in a given undirected graph G = (V, E). We prove that the simplex algorithm finds an optimal solution in at most m-n+1 (m = vertical bar E vertical bar, n = vertical bar V vertical bar) iterations. We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.eninfo:eu-repo/semantics/closedAccessNetwork designsubmodular functionfundamental cut setslinear programmingArticle848383536WOS:000445810300019N/A