Perfect graphs and graph entropy: An updated survey (Q2758342)

This survey paper is an updated version of an earlier paper [\textit{G. Simonyi}, Graph entropy: A survey. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 20, 399-441 (1995; Zbl 0828.05001)] by the same author. In the paper, three equivalent definitions are given for the notion of graph entropy, a real valued function on finite graphs with a probability measure on its vertex set. A connection to information theory and to the theory of perfect graphs is explained. It is indicated how graph entropy can be used in the problem of sorting. The notion of graph entropy can be generalized to hypergraphs. This generalized notion is applied to the job scheduling problem. It is pointed out that the Shannon capacity and its generalization, the Sperner capacity also have close connection to graph entropy.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].