Recognition of a class of unimodular functions

DOI10.1016/0166-218X(90)90147-5zbMath0717.90049MaRDI QIDQ2638932

Dominique de Werra, Bruno Simeone, Maurice Cochand

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

totally unimodular matrixpseudo-Boolean functionspolynomial-time recognition algorithmextended graph

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem, Recognition problems for special classes of polynomials in 0-1 variables, A pseudo-Boolean consensus approach to nonlinear 0-1 optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• Unimodular functions
• Dualization of regular Boolean functions
• On unimodular matrices
• A Selection Problem of Shared Fixed Costs and Network Flows