Note on the computational complexity of least core concepts for min-cost spanning tree games | Zendy

Ulrich Faigle | Zendy; Walter Kern | Zendy; Daniël Paulusma | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Note on the computational complexity of least core concepts for min-cost spanning tree games

Author(s) -

Ulrich Faigle,

Walter Kern,

Daniël Paulusma

Publication year - 2000

Publication title -

mathematical methods of operations research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.524

H-Index - 48

eISSN - 1432-5217

pISSN - 1432-2994

DOI - 10.1007/s001860000059

Subject(s) - core (optical fiber) , spanning tree , tree (set theory) , computer science , computational complexity theory , minimum spanning tree , mathematics , mathematical optimization , combinatorics , algorithm , telecommunications

Various least core concepts including the classical least core of cooperative games are discussed. By a reduction from minimum cover problems, we prove that computing an element in these least cores is in general NP-hard for minimum cost spanning tree games. As a consequence, computing the nucleolus, the nucleon and the per-capita nucleolus of minimum cost spanning tree games is also NP-hard

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research