Premium
Submodularity of minimum‐cost spanning tree games
Author(s) -
Kobayashi Masayuki,
Okamoto Yoshio
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21540
Subject(s) - submodular set function , spanning tree , minimum spanning tree , tree (set theory) , computer science , mathematical optimization , steiner tree problem , minimum degree spanning tree , characterization (materials science) , mathematics , regular polygon , distributed minimum spanning tree , combinatorics , materials science , geometry , nanotechnology
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 © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(3), 231–238 2014