On graphs which can or cannot induce Chinese Postman games with a non-empty core

Autor:	Frieda Granot, Daniel Granot
Rok vydání:	2012
Předmět:	Vertex (graph theory) Discrete mathematics Traverse Applied Mathematics Existential quantification Chinese postman Cost allocation Combinatorics Strongly polynomial Discrete Mathematics and Combinatorics Core Undirected graph Cooperative game MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Discrete Applied Mathematics. 160:2054-2059
ISSN:	0166-218X
DOI:	10.1016/j.dam.2012.04.002
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e3f01a92a6ac97429e96dc43243f33e4 https://doi.org/10.1016/j.dam.2012.04.002 Zobrazit plný text záznamu Full Text from ScienceDirect