zbMATH — the first resource for mathematics

On the core of a traveling salesman cost allocation game. (English) Zbl 0675.90102
A traveling salesman game is considered. The aim is to allocate his trip cost among the customers. Stable allocations belong to the corresponding cooperative game core. The characteristic function for every coalition is given by the solution of the traveling salesman problem for these very customers. The emptiness of the core for hypohamiltonian graphs is proved. Three more graphs with empty core are shown. Sufficient conditions on a graph which ensure the nonemptiness of the core are given. They require that the graph contains no minor which is isomorphic to one of the three above graphs. If the graph satisfies these conditions it is possible to compute a core allocation by solving a linear program of polynomial dimensions.
Reviewer: N.Novikova

91A12 Cooperative games
90C35 Programming involving graphs or networks
05C38 Paths and cycles
Full Text: DOI
[1] Berge, C., Graphs and hypergraphs, (1973), North-Holland New York · Zbl 0483.05029
[2] Dirac, G.A., A property of 4-chromatic graphs and some remarks on critical graphs, J. London math. society, 17, 85-92, (1962) · Zbl 0046.41001
[3] Dror, M., Cost allocation: the traveling salesman, bin-packing, and the knapsack, () · Zbl 0711.90056
[4] Fonlupt, J.; Naddef, D., The traveling salesman problem in graphs with some excluded minors, () · Zbl 0780.05034
[5] Granot, D., A generalized linear production model: A unifying model, Mathematical programming, 34, 212-222, (1986) · Zbl 0604.90142
[6] Granot, D.; Huberman, G., Minimum cost spanning tree games, Mathematical programming, 21, 1-18, (1981) · Zbl 0461.90099
[7] Granot, D.; Huberman, G., On the core and nucleolus of M.C.S.T. games, Mathematical programming, 29, 323-347, (1984) · Zbl 0541.90099
[8] Megiddo, N., Cost allocation for Steiner trees, Networks, 8, 1-6, (1978) · Zbl 0378.90118
[9] Megiddo, N., Computational complexity and the game theory approach to cost allocation for a tree, Mathematics of operations research, 3, 189-196, (1978) · Zbl 0397.90111
[10] Potters, J.A.M.; Curiel, I.J.; Tijs, S.H., Traveling salesman games, () · Zbl 0749.90094
[11] Tamir, A., On the core of network synthesis games, () · Zbl 0722.90091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.