|
|
|
Nezawisimoe mnozhestwo naibol'shej moschnosti: Polinomial'nyj algoritm
|
(Buch) |
Dieser Artikel gilt, aufgrund seiner Grösse, beim Versand als 2 Artikel!
| Inhalt: |
| Predlagaetsq metod postroeniq maximal'nogo nezawisimogo mnozhestwa naibol'shej moschnosti, wychislitel'naq slozhnost' kotorogo polinomial'na. Zadachu o maximal'nom nezawisimom mnozhestwe naibol'shej moschnosti prinqto otnosit' k klassu NP-polnyh w oblasti teorii grafow. Pokazano, chto dlq rassmatriwaemoj zadachi otsechenie Gomori sowpadaet s ogranicheniem, sootwetstwuüschim odnomu iz ciklow nechötnoj dliny. Predlagaemyj algoritm i osobennosti rassmatriwaemoj zadachi, otlichaüschie eö ot obschej zadachi linejnogo programmirowaniq, pozwolqüt postroit' algoritmy s polinomial'noj wychislitel'noj slozhnost'ü. |
|
i.d.R. innert 7-14 Tagen versandfertig
Newsfeed | 
Facebook | 
Twitter
