ENTROPY SPLITTING FOR ANTIBLOCKING CORNERS AND PERFECT GRAPHS

被引：60

作者：

CSISZAR, I

KORNER, J

LOVASZ, L

MARTON, K

SIMONYI, G

机构：

[1] EOTVOS LORAND UNIV, DEPT COMP SCI, H-1088 BUDAPEST, HUNGARY

[2] PRINCETON UNIV, DEPT COMP SCI, PRINCETON, NJ 08544 USA

[3] ECOLE NATL SUPER TECH, DEPT INFORMAT, PARIS, FRANCE

来源：

COMBINATORICA | 1990年 / 10卷 / 01期

关键词：

AMS subject classification (1980): 05C15;

D O I：

10.1007/BF02122693

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We characterize pairs of convex sets A, B in the k-dimensional space with the property that every probability distribution (p1, ..., pk) has a repsesentation pt = a(i).b(i), a is-a-member-of, b is-a-member-of B. Minimal pairs with this property are antiblocking pairs of convex corners. This result is closely related to a new entropy concept. The main application is an information theoretic characterization of perfect graphs.

引用

页码：27 / 40

页数：14

共 16 条

[1]

Berge C., 1976, GRAPHS HYPERGRAPHS

[2] CERTAIN POLYTOPES ASSOCIATED WITH GRAPHS [J].

CHVATAL, V .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 18 (02) :138-154

[3]

Fulkerson D. R., 1971, MATH PROGRAM, V1, P168

[4]

FULKERSON DR, 1973, MATH PROGRAM, P69

[5] RELAXATIONS OF VERTEX PACKING [J].

GROTSCHEL, M ;

LOVASZ, L ;

SCHRIJVER, A .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 40 (03) :330-343

[6]

KORNER J, 1986, SIAM J ALGEBRA DISCR, V7, P560

[7] 2-STEP ENCODING FOR FINITE SOURCES [J].

KORNER, J ;

LONGO, G .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1973, 19 (06) :778-782

[8]

Korner J., 1973, PROC 6 PRAGUE C INF, P411

[9]

Korner J., 1973, STUDIA MATH HUNG, V8, P405

[10]

KORNER J, 1986, REND I MATEM U TRIES, V18, P117

← 1 2 →