ISBN-13: 9783843301428 / Rosyjski / Miękka / 2010 / 88 str.
V knige rassmatrivaetsya problema opredeleniya granitsy mezhdu polinomialnoy razreshimostyu i NP-polnotoy dlya klassicheskikh grafovykh zadach v reshetke zamknutykh otnositelno udaleniya vershin klassov obyknovennykh grafov (reshetke nasledstvennykh klassov). Izuchenie dannoy granitsy vedetsya na osnove metoda kriticheskogo klassa grafov - poiska nasledstvennykh klassov, igrayushchikh osobuyu rol pri reshenii upomyanutoy zadachi demarkatsii. Issleduyutsya dva tipa takikh razdeliteley - granichnye i minimalnye slozhnye klassy grafov, odin iz kotorykh (minimalnye slozhnye klassy) byl vveden v rassmotrenie avtorom. V monografii predstavleny rezultaty avtora po strukture granichnykh klassov dlya ryada zadach na grafakh. Naprimer, pokazyvaetsya, chto dlya obeikh zadach o 3-raskraske (vershinnogo i rebernogo variantov) mnozhestvo granichnykh klassov kontinualno. V etoy knige vpervye pred"yavleny konkretnye primery minimalnykh slozhnykh klassov (ranee ne bylo izvestno, sushchestvuyut li oni voobshche). S drugoy storony, vydelyaetsya tip zadach, dlya kotorykh takikh ne sushchestvuet. Dannaya kniga prednaznachena dlya studentov, aspirantov i nauchnykh rabotnikov, zanimayushchikhsya diskretnoy matematikoy.