Submodularity of minimum-cost spanning tree games

被引：7
作者：
Kobayashi, Masayuki [1 ]
Okamoto, Yoshio [2 ]
机构：
[1] Toyohashi Univ Technol, Dept Informat & Comp Sci, Tempaku Ku, Toyohashi, Aichi 4418580, Japan
[2] Univ Electrocommun, Dept Commun Engn & Informat, Grad Sch Informat & Engn, Chofu, Tokyo 1828585, Japan
来源：
NETWORKS | 2014年 / 63卷 / 03期
基金：
日本学术振兴会;
关键词：
convex game; submodularity; cooperative game; minimum-cost spanning tree game; cost allocation; COMBINATORIAL OPTIMIZATION GAMES; ALLOCATION;
D O I：
10.1002/net.21540
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We give a necessary condition and a sufficient condition for a minimum-cost spanning tree game introduced by Bird to be submodular (or convex). When the cost is restricted to two values, we give a characterization of submodular minimum-cost spanning tree games. We also discuss algorithmic issues.Copyright (c) 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(3), 231-238 2014
引用
收藏
页码：231 / 238
页数：8
相关论文
共 50 条
12345