Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr.:
Year:
Volume:
Issue:
Page:
Find






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


Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya, 2023, Volume 19, Issue 1, Pages 90–108
DOI: https://doi.org/10.21638/11701/spbu10.2023.108
(Mi vspui569)
 

Computer science

Algorithm for optimal coloring of square $(0,1)$-matrices

I. V. Olemskoy, O. S. Firyulina

St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation
References:
Abstract: The paper proposes an algorithm for solving the configuration-optimization coloring problem for square $(0,1)$-matrices, which is based on the method of selection their structural features. The algorithm belongs to the method's of backtracking, however, the construction of the optimal solution is carried out among the options that provide a certain configuration, due to which the size of the search tree is significantly reduced. A detailed scheme of its operation is given, and the effectiveness of the solution is demonstrated by the example of calculating the chromatic number of a specific $(0,1)$-matrix.
Keywords: graph coloring, chromatic number, $(0,1)$-matrix.
Received: December 1, 2022
Accepted: January 19, 2023
Document Type: Article
UDC: 519.174, 519.854.64
MSC: 05C15, 05C85
Language: Russian
Citation: I. V. Olemskoy, O. S. Firyulina, “Algorithm for optimal coloring of square $(0,1)$-matrices”, Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr., 19:1 (2023), 90–108
Citation in format AMSBIB
\Bibitem{OleFir23}
\by I.~V.~Olemskoy, O.~S.~Firyulina
\paper Algorithm for optimal coloring of square $(0,1)$-matrices
\jour Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr.
\yr 2023
\vol 19
\issue 1
\pages 90--108
\mathnet{http://mi.mathnet.ru/vspui569}
\crossref{https://doi.org/10.21638/11701/spbu10.2023.108}
Linking options:
  • https://www.mathnet.ru/eng/vspui569
  • https://www.mathnet.ru/eng/vspui/v19/i1/p90
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления
    Statistics & downloads:
    Abstract page:25
    Full-text PDF :8
    References:9
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024