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 条
  • [21] Minimum cost spanning tree problems with groups
    Gustavo Bergantiños
    María Gómez-Rúa
    Economic Theory, 2010, 43 : 227 - 262
  • [22] Additivity in minimum cost spanning tree problems
    Bergantinos, Gustavo
    Vidal-Puga, Juan
    JOURNAL OF MATHEMATICAL ECONOMICS, 2009, 45 (1-2) : 38 - 42
  • [23] Geometric Minimum Diameter Minimum Cost Spanning Tree Problem
    Seo, Dae Young
    Lee, D. T.
    Lin, Tien-Ching
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5878 : 283 - +
  • [24] Split Manipulations in Cost Sharing of Minimum Cost Spanning Tree
    Todo, Taiki
    Yokoo, Makoto
    ECAI 2020: 24TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2020, 325 : 219 - 226
  • [25] Noncooperative Cost Spanning Tree Games with Budget Restrictions
    Bergantinos, Gustavo
    Lorenzo, Leticia
    NAVAL RESEARCH LOGISTICS, 2008, 55 (08) : 747 - 757
  • [26] MINIMUM-COST CHOKES
    ODDIE, TH
    SALPETER, JL
    PHILIPS RESEARCH REPORTS, 1947, 2 (04): : 281 - 312
  • [27] An egalitarian solution to minimum cost spanning tree problems
    Emre Doğan
    İbrahim Barış Esmerok
    International Journal of Game Theory, 2024, 53 : 127 - 141
  • [28] An egalitarian solution to minimum cost spanning tree problems
    Dogan, Emre
    Esmerok, Ibrahim Baris
    INTERNATIONAL JOURNAL OF GAME THEORY, 2024, 53 (01) : 127 - 141
  • [29] THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE
    徐绪松
    刘大成
    吴丽华
    ActaMathematicaScientia, 1996, (03) : 296 - 301
  • [30] Minimum cost spanning tree problems with indifferent agents
    Trudeau, Christian
    GAMES AND ECONOMIC BEHAVIOR, 2014, 84 : 137 - 151
12345