Király Zoltán: Csúcsok lefedése párosításokkal

Először vázoljuk, hogy milyen integrált áramkör-készítési folyamat vetette fel
a címben feltett kérdést.
Utána röviden ismertetjük Wang, Song és Yuan cikkét, akik (kicsit
túlbonyolított) algoritmust adtak a legkisebb k meghatározására, hogy k
párosítással fedhetőek legyenek a csúcsok.

Majd klasszikus eredményeket ismertetünk (helyenként új bizonyítással).
Ezek segítségével arra az esetre, ha a minimum nem 1, jobb algoritmust adunk,
valamint szép minimax tételt. A végén a súlyozott esetről lesz szó, nemnegatív
élsúlyok esetén tudunk minimalizálni (a k párosítással fedés össz-élsúlyát),
általában pedig megmutatjuk, hogy ez NP-nehéz.