Kinų Laiškanešio problema mišriems grafams, sudėtingumas

Aš žinau, kad ši laiškanešio problema mišriems grafams yra NP-pilnumo ( tai  yra nėra polinominio laiko algoritmo). Šios problemos formuluotę galima rasti čia: http://www.csc.kth.se/~viggo/wwwcompendium/node109.html . Ir aš turiu užduotį - apskaičiuoti operacijų skaičių pilnam perrinkimui ("Brute  force" algoritmo sudėtingumas). Kaip aš galėčiau tai padaryti? Kaip pradėti norint išspręsti šį uždavinį? Ačiū.

Dičiūnas? Teks arba bandyti ieškoti mokslinių straipsnių (bet nemanau, kad ten bus aprašytas brute force algoritmas) arba pačiam sugalvoti brute force algoritmą. Tiesiog teks apeiti grafą visais įmanomais būdais. Gal bus paprasčiau jei prieš tai transformuosi jį į paprastą orientuotą grafą (tam sugalvosi polinominio sudėtingumo algoritmą, kuris neturės įtakos viso algoritmo sudėtingumui).