SKDIM sazetak 20141218

Izvor: KiWi

Za razliku od savršenih i najduljih (eng. maximum matching) sparivanja, maksimalna sparivanja (eng. maximal matching) nisu dobro istražena. Glavni razlog je u nelokalnim efektima koji otežavaju izgradnju strukturne teorije koja je razvijena za savršena i najdulja sparivanja. Nelokalni efekti rezultiraju i rekurzijama koje se ne daju analizirati metodama pogodnima za rekurzije koje se javljaju kod najduljih sparivanja, a to pak negativno utječe na dobivanje enumerativnih rezultata. Predstavit ćemo enumerativne rezultate za pojedine klase grafova.