18,99 €
inkl. MwSt.

Versandfertig in 6-10 Tagen
  • Broschiertes Buch

Predlagaetsya metod postroeniya maximal'nogo nezavisimogo mnozhestva naibol'shej moshhnosti, vychislitel'naya slozhnost' kotorogo polinomial'na. Zadachu o maximal'nom nezavisimom mnozhestve naibol'shej moshhnosti prinyato otnosit' k klassu NP-polnyh v oblasti teorii grafov. Pokazano, chto dlya rassmatrivaemoj zadachi otsechenie Gomori sovpadaet s ogranicheniem, sootvetstvujushhim odnomu iz ciklov nechjotnoj dliny. Predlagaemyj algoritm i osobennosti rassmatrivaemoj zadachi, otlichajushhie ejo ot obshhej zadachi linejnogo programmirovaniya, pozvolyajut postroit' algoritmy s polinomial'noj vychislitel'noj slozhnost'ju.…mehr

Produktbeschreibung
Predlagaetsya metod postroeniya maximal'nogo nezavisimogo mnozhestva naibol'shej moshhnosti, vychislitel'naya slozhnost' kotorogo polinomial'na. Zadachu o maximal'nom nezavisimom mnozhestve naibol'shej moshhnosti prinyato otnosit' k klassu NP-polnyh v oblasti teorii grafov. Pokazano, chto dlya rassmatrivaemoj zadachi otsechenie Gomori sovpadaet s ogranicheniem, sootvetstvujushhim odnomu iz ciklov nechjotnoj dliny. Predlagaemyj algoritm i osobennosti rassmatrivaemoj zadachi, otlichajushhie ejo ot obshhej zadachi linejnogo programmirovaniya, pozvolyajut postroit' algoritmy s polinomial'noj vychislitel'noj slozhnost'ju.
Autorenporträt
Murat Huseewich Dudow, docent SewKawGGTA, g. Cherkessk, Karachaewo-Cherkesskaq Respublika