User Tools

Site Tools


Ryan McCullogh (Binghamton)

Conservation, Potentials, and the Postman Structure of Graphs

Abstract for the Combinatorics Seminar 2010 December 13

A notion of “conservativeness”, defined for graphs with integrally weighted edges, leads to significant new understanding of the Chinese Postman Problem. A weighted graph is conservative if the sum of weights around every cycle is non-negative. (This is different from the normal definition of conservation.) A potential is a vertex function that upholds the edge weights in a certain sense. The talk will explain these concepts and present some results about them, all from a paper of Andras Sebo.

seminars/comb/abstract.201012mcc.txt · Last modified: 2020/01/29 14:03 (external edit)