Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретный анализ и исследование операций, сер. 1, 2003, том 10, выпуск 3, страницы 54–66 (Mi da137)  

Две задачи на наследственных системах

В. П. Ильев, А. С. Талевнин

Омский государственный университет им. Ф. М. Достоевского
Список литературы:
Аннотация: Исследуются задачи о максимальном независимом и минимальном зависимом множестве наследственной системы, которые могут быть рассмотрены как задачи о максимальном независимом множестве вершин и минимальном вершинном покрытии в гиперграфе соответственно. Для приближенного решения невзвешенной задачи о независимом множестве предложен алгоритм градиентного типа. В предположении, что гиперграф не содержит ребер мощности 1, доказано, что этот алгоритм всегда дает решение, которое не более чем в $(\bar d+2)/2$ раз хуже оптимального, где $\bar d$ – средняя степень вершин гиперграфа. Показана эквивалентность задачи о минимальном зависимом множестве задаче о покрытии множества, что позволяет применить для ее решения известный алгоритм Хватала. Этот алгоритм находит решение, отличающееся от оптимального не более чем в $1+\ln\Delta$ раз, где $\Delta$ – максимальная степень вершин гиперграфа.
Статья поступила: 15.05.2003
Переработанный вариант: 06.06.2003
Реферативные базы данных:
УДК: 519.8
Образец цитирования: В. П. Ильев, А. С. Талевнин, “Две задачи на наследственных системах”, Дискретн. анализ и исслед. опер., сер. 1, 10:3 (2003), 54–66
Цитирование в формате AMSBIB
\RBibitem{IleTel03}
\by В.~П.~Ильев, А.~С.~Талевнин
\paper Две задачи на наследственных системах
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2003
\vol 10
\issue 3
\pages 54--66
\mathnet{http://mi.mathnet.ru/da137}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2020832}
\zmath{https://zbmath.org/?q=an:1099.90032}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da137
  • https://www.mathnet.ru/rus/da/v10/s1/i3/p54
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:316
    PDF полного текста:111
    Список литературы:32
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024