UNIMODULAR FUNCTIONS

被引：22

作者：

HANSEN, P ^{[1
]}

SIMEONE, B ^{[1
]}

机构：

[1] UNIV ROME,DEPT STAT,I-00100 ROME,ITALY

来源：

DISCRETE APPLIED MATHEMATICS | 1986年 / 14卷 / 03期

关键词：

COMPUTER PROGRAMMING - Algorithms - MATHEMATICAL TECHNIQUES - Graph Theory;

D O I：

10.1016/0166-218X(86)90031-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We introduce some clases of pseudo-boolean functions (the so-called 'unimodular', completely unimodular' and 'unate' ones), whose maximization over the binary n-cubes is reducible to a maximal flow problem. It is shown that in the quadratic case the three classes coincide, and that they also coincide with the class of those pseudo-boolean functions f such that a certain signed graph G//f associated with f is balanced. The latter characterization leads to a polynomial recognition algorithm. When G//f is a (signed) tree, a linear-time maximization algorithm is available.

引用

页码：269 / 281

页数：13

共 22 条

[1] SELECTION PROBLEM [J].

BALINSKI, ML .

MANAGEMENT SCIENCE SERIES A-THEORY, 1970, 17 (03) :230-231

[2]

Berge C., 1973, GRAPHS HYPERGRAPHS, V7

[3] MAXIMIZING A SUPERMODULAR PSEUDOBOOLEAN FUNCTION - A POLYNOMIAL ALGORITHM FOR SUPERMODULAR CUBIC FUNCTIONS [J].

BILLIONNET, A ;

MINOUX, M .

DISCRETE APPLIED MATHEMATICS, 1985, 12 (01) :1-11

[4]

CHERKASKY BV, 1977, MATH METHODS SOLUTIO, V7, P117

[5]

FISHER ML, 1978, MATH PROGRAM, V14, P265

[6]

Garey M. R., 1978, COMPUTERS INTRACTABI

[7]

HAMMER PL, 1963, STUDI SI CERCETARI M, V14, P59

[8]

HAMMER PL, 1980, ANN DISCRETE MATH, V8, P107

[9]

HAMMER PL, 1974, NUMERISCHE METHODEN, V2, P51

[10]

HANSEN P, 1973, C STRUCTURES EC ECON

← 1 2 3 →