Loading [MathJax]/jax/output/CommonHTML/jax.js
Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretnyi Analiz i Issledovanie Operatsii, 2021, Volume 28, Issue 1, Pages 15–47
DOI: https://doi.org/10.33048/daio.2021.28.685
(Mi da1272)
 

This article is cited in 1 scientific paper (total in 1 paper)

Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes

O. O. Razvenskaya, D. S. Malyshev

National Research University “Higher School of Economics”, 25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
Full-text PDF (457 kB) Citations (1)
References:
Abstract: The weighted vertex coloring problem for a given weighted graph is to minimize the number of used colors so that for each vertex the number of the colors that are assigned to this vertex is equal to its weight and the assigned sets of vertices are disjoint for any adjacent vertices. For all but four hereditary classes that are defined by two connected 5-vertex induced prohibitions, the computational complexity is known of the weighted vertex coloring problem with unit weights. For four of the six pairwise intersections of these four classes, the solvability was proved earlier of the weighted vertex coloring problem in time polynomial in the sum of the vertex weights. Here we justify this fact for the remaining two intersections. Bibliogr. 17.
Keywords: weighted vertex coloring problem, hereditary class, computational complexity.
Funding agency Grant number
Russian Science Foundation 19-71-00005
This research is supported by the Russian Science Foundation (Project 19–71–00005).
Received: 29.04.2020
Revised: 03.11.2020
Accepted: 05.11.2020
English version:
Journal of Applied and Industrial Mathematics, 2021, Volume 15, Issue 1, Pages 97–117
DOI: https://doi.org/10.1134/S1990478921010099
Bibliographic databases:
Document Type: Article
UDC: 519.17
Language: Russian
Citation: O. O. Razvenskaya, D. S. Malyshev, “Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes”, Diskretn. Anal. Issled. Oper., 28:1 (2021), 15–47; J. Appl. Industr. Math., 15:1 (2021), 97–117
Citation in format AMSBIB
\Bibitem{RazMal21}
\by O.~O.~Razvenskaya, D.~S.~Malyshev
\paper Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes
\jour Diskretn. Anal. Issled. Oper.
\yr 2021
\vol 28
\issue 1
\pages 15--47
\mathnet{http://mi.mathnet.ru/da1272}
\crossref{https://doi.org/10.33048/daio.2021.28.685}
\transl
\jour J. Appl. Industr. Math.
\yr 2021
\vol 15
\issue 1
\pages 97--117
\crossref{https://doi.org/10.1134/S1990478921010099}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85104706415}
Linking options:
  • https://www.mathnet.ru/eng/da1272
  • https://www.mathnet.ru/eng/da/v28/i1/p15
  • This publication is cited in the following 1 articles:
    1. D. S. Malyshev, O. I. Duginov, “A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs”, J. Appl. Industr. Math., 17:4 (2023), 791–801  mathnet  crossref  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024