𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Equivalence between the minimum covering problem and the maximum matching problem

✍ Scribed by Ján Plesník

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
127 KB
Volume
49
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The minimum covering problem in weighted graphs with n vertices is transformed in time O(n 2) to the maximum matching problem with n or n + 1 vertices, and conversely.

📜 SIMILAR VOLUMES

The Minimum Equivalent DNF Problem and S
The Minimum Equivalent DNF Problem and Shortest Implicants
✍ Christopher Umans 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 149 KB

We prove that the Minimum Equivalent DNF problem is S P 2 -complete, resolving a conjecture due to Stockmeyer. We also consider the complexity and approximability of a related optimization problem in the second level of the polynomial hierarchy, that of finding shortest implicants of a Boolean funct

A dual algorithm for the minimum coverin
A dual algorithm for the minimum covering ball problem in
✍ P.M. Dearing; Christiane R. Zeck 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 953 KB

A dual type algorithm constructs the minimum covering ball of a given finite set of points in R n by finding the minimum covering balls of a sequence of subsets, each with no more than n + 1 points and with strictly increasing radius, until all points are covered.

The gradual covering problem
The gradual covering problem
✍ Zvi Drezner; George O. Wesolowsky; Tammy Drezner 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB