Computing the Nucleolus of Min-Cost Spanning Tree Games Is NP-Hard

摘要

The authors prove that computing the nucleolus of minimum cost spanning tree211u001egames is in general NP-hard. The proof uses a reduction from minimum cover 211u001eproblems.