\input zb-basic
\input zb-ioport
\iteman{io-port 06064594}
\itemau{Granot, Daniel; Granot, Frieda}
\itemti{On graphs which can or cannot induce Chinese Postman games with a non-empty core.}
\itemso{Discrete Appl. Math. 160, No. 13-14, 2054-2059 (2012).}
\itemab
Summary: We study the Chinese postman (CP) cooperative game induced by a connected, weighted, undirected graph $G$, wherein players reside at the edges of $G$ and a postman, starting from a post-office location (i.e., a vertex of $G$), 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.
\itemrv{~}
\itemcc{}
\itemut{cooperative game; cost allocation; core; chinese postman}
\itemli{doi:10.1016/j.dam.2012.04.002}
\end