Задачи оптимизации на графах с интервальными параметрами

• Published in: Кибернетика и системный анализ
• Date: 2009
• Main Authors: Перепелица, В.А., Козин, И.В., Максишко, Н.К.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2009
• Subjects: Кибернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/44339
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Задачи оптимизации на графах с интервальными параметрами / В.А. Перепелица, И.В. Козин, Н.К. Максишко // Кибернетика и системный анализ. — 2009. — № 2. — С. 3-14. — Бібліогр.: 19 назв. — рос.

Розглянуто відомі задачі оптимізації на графах в умовах невизначеності, коли область значень параметрів задана у вигляді інтервалів. Обґрунтовано експоненційні оцінки обчислювальної складності досліджуваних задач, а також задач, що в класичній постановці є поліноміальними. Знайдено поліноміально роз...