The \(k\)-centrum Chinese postman delivery problem and a related cost allocation game

DOI10.1016/j.dam.2014.07.021zbMath1303.91029OpenAlexW1993094949MaRDI QIDQ477339

Frieda Granot, Daniel Granot, Harshavardhan Ravichandran

Publication date: 3 December 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.07.021

zbMATH Keywords

coreChinese postman problem\(k\)-centrum Chinese postman problemChinese postman gamesubmodular game

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Cooperative games (91A12) Games involving graphs (91A43) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Revisiting \(k\)-sum optimization, On games arising from multi-depot Chinese postman problems

Cites Work

• On graphs which can or cannot induce Chinese Postman games with a non-empty core
• On Chinese postman games where residents of each road pay the cost of their road
• On the concavity of delivery games
• Cost allocation in the Chinese postman problem
• On the equivalence between some local and global Chinese postman and traveling salesman graphs
• Minimizing the sum of the \(k\) largest functions in linear time.
• On \(k\)-sum optimization
• On some balanced, totally balanced and submodular delivery games
• Cores of convex games
• Algorithms for two bottleneck optimization problems
• Minimum cost spanning tree games
• On the core of linear production games
• On cost allocation for a spanning tree: A game theoretic approach
• A fundamental problem in vehicle routing
• The bottleneck transportation problem
• The \(k\)-centrum multi-facility location problem