Mincut ideals of two-terminal networks
- Sáenz-De-Cabezón, E. 2
- Wynn, H.P. 1
-
1
London School of Economics and Political Science
info
-
2
Universidad de La Rioja
info
ISSN: 0938-1279
Year of publication: 2010
Volume: 21
Issue: 6
Pages: 443-457
Type: Article
More publications in: Applicable Algebra in Engineering, Communications and Computing
Abstract
This paper introduces mincut ideals of two-terminal networks, which arise in the algebraic analysis of system reliability. We give the definitions and study their algebraic and combinatorial properties in some particular cases. It turns out that some features of the mincut ideals arising from networks such as the Cohen-Macaulay property and the computation of Betti numbers, which are important in tight reliability bounds, have a compact expression for series-parallel networks. This relies on a natural mapping of the structure of such networks into the union and intersection structure of the corresponding ideal. © Springer-Verlag 2010.