Submodularity of minimum-cost spanning tree games
2014; Wiley; Volume: 63; Issue: 3 Linguagem: Inglês
10.1002/net.21540
ISSN1097-0037
AutoresMasayuki Kobayashi, Yoshio Okamoto,
Tópico(s)Advanced Graph Theory Research
ResumoNetworksVolume 63, Issue 3 p. 231-238 Research Article Submodularity of minimum-cost spanning tree games Masayuki Kobayashi, Masayuki Kobayashi Department of Information and Computer Sciences, Toyohashi University of Technology, Hibarigaoka 1–1, Tempaku,Toyohashi, Aichi, 441–8580 JapanSearch for more papers by this authorYoshio Okamoto, Corresponding Author Yoshio Okamoto Department of Information and Computer Sciences, Toyohashi University of Technology, Hibarigaoka 1–1, Tempaku,Toyohashi, Aichi, 441–8580 JapanCorrespondence to: Y. Okamoto; e-mail: okamotoy@uec.ac.jpSearch for more papers by this author Masayuki Kobayashi, Masayuki Kobayashi Department of Information and Computer Sciences, Toyohashi University of Technology, Hibarigaoka 1–1, Tempaku,Toyohashi, Aichi, 441–8580 JapanSearch for more papers by this authorYoshio Okamoto, Corresponding Author Yoshio Okamoto Department of Information and Computer Sciences, Toyohashi University of Technology, Hibarigaoka 1–1, Tempaku,Toyohashi, Aichi, 441–8580 JapanCorrespondence to: Y. Okamoto; e-mail: okamotoy@uec.ac.jpSearch for more papers by this author First published: 27 January 2014 https://doi.org/10.1002/net.21540Citations: 6Read the full textAboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinked InRedditWechat Abstract 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 Citing Literature Volume63, Issue3May 2014Pages 231-238 RelatedInformation
Referência(s)