Affordable Access

Computing the minimal covering set

  • Computer Science


We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set-the minimal upward covering set and the minimal downward covering set-unless P equals NP. Finally, we observe a strong relationship between von Neumann-Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

Computing the minimal covering set

on Mathematical Social Sciences Jan 01, 2008

On the minimal covering of infinite sets

on Discrete Applied Mathematics Jan 01, 1993
More articles like this..