Submodularity of minimum‐cost spanning tree games | Zendy

Kobayashi Masayuki | Zendy; Okamoto Yoshio | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research