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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 1, 2006, том 13, номер 1, страницы 33–44 (Mi da22)  

Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

О раскраске инциденторов в ориентированном взвешенном мультиграфе

В. Г. Визинг, А. В. Пяткинa

a Институт математики им. С. Л. Соболева СО РАН

Аннотация: Правильная раскраска инциденторов ориентированного взвешенного мультиграфа называется допустимой, если разность между цветами конечного и начального инциденторов каждой дуги не меньше веса этой дуги. Наименьшее число цветов, необходимое для допустимой раскраски инциденторов, называется инциденторным хроматическим числом мультиграфа. Исследуется задача отыскания инциденторного хроматического числа ориентированного мультиграфа. Доказывается NP-полнота этой задачи. Найдены верхние оценки для инциденторного хроматического числа. Приводится приближённый полиномиальный алгоритм решения задачи с максимальной относительной погрешностью, меньшей 2.
Библ. 7.

Полный текст: PDF файл (256 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
УДК: 519.718
Статья поступила: 21.09.2005

Образец цитирования: В. Г. Визинг, А. В. Пяткин, “О раскраске инциденторов в ориентированном взвешенном мультиграфе”, Дискретн. анализ и исслед. опер., сер. 1, 13:1 (2006), 33–44

Цитирование в формате AMSBIB
\RBibitem{VizPya06}
\by В.~Г.~Визинг, А.~В.~Пяткин
\paper О раскраске инциденторов в~ориентированном взвешенном мультиграфе
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2006
\vol 13
\issue 1
\pages 33--44
\mathnet{http://mi.mathnet.ru/da22}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2258902}
\zmath{https://zbmath.org/?q=an:1249.05254}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da22
  • http://mi.mathnet.ru/rus/da/v13/s1/i1/p33

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. В. Г. Визинг, “Об оценках инциденторного хроматического числа взвешенного ориентированного мультиграфа”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 13:4 (2006), 18–25  mathnet  mathscinet  zmath; V. G. Vizing, “On bounds for the incidentor chromatic number of a directed weighted multigraph”, J. Appl. Industr. Math., 1:4 (2007), 504–508  crossref
    2. В. Г. Визинг, А. В. Пяткин, “Об оценках инциденторного хроматического числа взвешенного неориентированного мультиграфа”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 14:2 (2007), 3–15  mathnet  mathscinet  zmath; J. Appl. Industr. Math., 2:3 (2008), 432–439  crossref
    3. А. В. Пяткин, “О предписанной раскраске инциденторов в мультиграфе степени 3”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 14:3 (2007), 80–89  mathnet  mathscinet  zmath; J. Appl. Industr. Math., 2:4 (2008), 560–565  crossref
    4. В. Г. Визинг, “О мультираскраске инциденторов взвешенного ориентированного мультиграфа”, Дискретн. анализ и исслед. опер., 21:4 (2014), 33–41  mathnet  mathscinet; V. G. Vizing, “On multicoloring of incidentors of a weighted oriented multigraph”, J. Appl. Industr. Math., 8:4 (2014), 604–608  crossref
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:451
    Полный текст:92
    Литература:38
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020