Dmitrij Malyshew

Metod «kriticheskogo» klassa grafow

Poisk predelow äffektiwnoj razreshimosti w reshetke nasledstwenno zamknutyh klassow

• Broschiertes Buch

Produktbeschreibung

V knige rassmatriwaetsq problema opredeleniq granicy mezhdu polinomial'noj razreshimost'ü i NP-polnotoj dlq klassicheskih grafowyh zadach w reshetke zamknutyh otnositel'no udaleniq wershin klassow obyknowennyh grafow (reshetke nasledstwennyh klassow). Izuchenie dannoj granicy wedetsq na osnowe metoda «kriticheskogo» klassa grafow ¿ poiska nasledstwennyh klassow, igraüschih osobuü rol' pri reshenii upomqnutoj zadachi demarkacii. Issleduütsq dwa tipa takih razdelitelej ¿ granichnye i minimal'nye slozhnye klassy grafow, odin iz kotoryh (minimal'nye slozhnye klassy) byl wweden w rassmotrenie awtorom. V monografii predstawleny rezul'taty awtora po strukture granichnyh klassow dlq rqda zadach na grafah. Naprimer, pokazywaetsq, chto dlq obeih zadach o 3-raskraske (wershinnogo i rebernogo wariantow) mnozhestwo granichnyh klassow kontinual'no. V ätoj knige wperwye pred#qwleny konkretnye primery minimal'nyh slozhnyh klassow (ranee ne bylo izwestno, suschestwuüt li oni woobsche). S drugoj storony, wydelqetsq tip zadach, dlq kotoryh takih ne suschestwuet. Dannaq kniga prednaznachena dlq studentow, aspirantow i nauchnyh rabotnikow, zanimaüschihsq diskretnoj matematikoj.

Produktdetails

• Verlag: LAP LAMBERT Academic Publishing
• Seitenzahl: 88
• Erscheinungstermin: 1. Oktober 2010
• Russisch
• Abmessung: 220mm x 150mm x 6mm
• Gewicht: 149g
• ISBN-13: 9783843301428
• ISBN-10: 3843301425
• Artikelnr.: 62762759

Autorenporträt

Malyshew Dmitrij Sergeewich (rod. 29.10.1985), k.f.-m.n. (2009), doc. kaf. PMI NF GU-VShJe i st. pr. kaf. MLiVA NNGU im. N.I. Lobachewskogo. Oblast' nauchnyh interesow: teoriq grafow, teoriq slozhnosti wychislenij. Prepodawaemye discipliny: diskretnaq matematika, analiz i razrabotka algoritmow, diskretnye modeli i algoritmy.