Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418438 | Discrete Applied Mathematics | 2012 | 6 Pages |
Abstract
We study the Chinese postman (CP) cooperative game induced by a connected, weighted, undirected graph GG, wherein players reside at the edges of GG and a postman, starting from a post-office location (i.e., a vertex of GG), needs to traverse all edges before returning to the post-office. We provide a complete characterization of all connected graphs for which there exists a positive edge-cost function such that the induced CP game has a non-empty core, and, consequently, we derive a complete characterization of all connected graphs for which there does not exist a positive edge-cost function which induces a CP game with a non-empty core. Membership in these classes of graphs can be verified in strongly polynomial time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Granot, Frieda Granot,