|
Дискретн. анализ и исслед. опер., сер. 1, 2007, том 14, номер 2, страницы 3–15
(Mi da46)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Об оценках инциденторного хроматического числа взвешенного неориентированного мультиграфа
В. Г. Визинг, А. В. Пяткинa a Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Правильная раскраска инциденторов неориентированного взвешенного мультиграфа называется допустимой, если модуль разности между цветами инциденторов каждого ребра не меньше веса этого ребра. Наименьшее число цветов, необходимое для допустимой раскраски инциденторов, называется инциденторным хроматическим числом мультиграфа. Исследуется задача отыскания этого числа. Доказана NP-трудность этой задачи для $\Delta$ цветов. Найдены верхние и нижние оценки для инциденторного хроматического числа.
Полный текст:
PDF файл (283 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2008, 2:3, 432–439
Реферативные базы данных:
УДК:
519.718 Статья поступила: 08.11.2006
Образец цитирования:
В. Г. Визинг, А. В. Пяткин, “Об оценках инциденторного хроматического числа взвешенного неориентированного мультиграфа”, Дискретн. анализ и исслед. опер., сер. 1, 14:2 (2007), 3–15; J. Appl. Industr. Math., 2:3 (2008), 432–439
Цитирование в формате AMSBIB
\RBibitem{VizPya07}
\by В.~Г.~Визинг, А.~В.~Пяткин
\paper Об оценках инциденторного хроматического числа взвешенного неориентированного мультиграфа
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2007
\vol 14
\issue 2
\pages 3--15
\mathnet{http://mi.mathnet.ru/da46}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2368728}
\zmath{https://zbmath.org/?q=an:1249.05149}
\transl
\jour J. Appl. Industr. Math.
\yr 2008
\vol 2
\issue 3
\pages 432--439
\crossref{https://doi.org/10.1134/S1990478908030149}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-52749092483}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da46 http://mi.mathnet.ru/rus/da/v14/s1/i2/p3
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
В. Г. Визинг, “О мультираскраске инциденторов взвешенного неориентированного мультиграфа”, Дискретн. анализ и исслед. опер., 19:4 (2012), 35–47
; V. G. Vizing, “Multicoloring of incidentors of weighted undirected multigraph”, J. Appl. Industr. Math., 6:4 (2012), 514–521
|
Просмотров: |
Эта страница: | 248 | Полный текст: | 75 | Литература: | 22 |
|