Logo BSU

  1. Электронная библиотека БГУ
  2. Факультет прикладной математики и информатики
  3. НАУЧНЫЕ ПУБЛИКАЦИИ ФАКУЛЬТЕТА ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ
  4. Статьи факультета прикладной математики и информатики
Даты публикации Авторы Заглавия Темы
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ: https://elib.bsu.by/handle/123456789/291303
Полная запись метаданных
Поле DCЗначениеЯзык
dc.contributor.authorДугинов, О. И.-
dc.contributor.authorХимич, С. С.-
dc.date.accessioned2022-12-28T06:47:22Z-
dc.date.available2022-12-28T06:47:22Z-
dc.date.issued2022-
dc.identifier.citationProc Natl Acad Sci Belarus Phys Math Ser 2022;58(2):155-168.ru
dc.identifier.urihttps://elib.bsu.by/handle/123456789/291303-
dc.description.abstractИзучается вычислительная сложность задачи разбиения ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4, в специальных классах графов. Задача относится к числу NP-трудных и находит применение при организации распределения сетевых пакетов по каналам связи в процессе передачи от одного маршрутизатора к другому. Разработан алгоритм, решающий задачу в классе деревьев порядка n за время O(n log n). Выделены трудноразрешимые случаи задачи.ru
dc.language.isoruru
dc.publisherBelaruskaya Navukaru
dc.rightsinfo:eu-repo/semantics/openAccessru
dc.subjectЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математикаru
dc.titleРАЗБИЕНИЕ РЕБЕР ДВУДОЛЬНОГО ГРАФА НА НАИМЕНЬШЕЕ ЧИСЛО ПОДГРАФОВ, ИЗОМОРФНЫХ ПОДГРАФАМ ПРОСТОГО ЦИКЛА ПОРЯДКА 4ru
dc.title.alternativePARTITIONING THE EDGE SET OF A BIPARTITE GRAPH INTO THE MINIMAL NUMBER OF SUBGRAPHS ISOMORPHIC TO THOSE OF A SIMPLE 4 ORDER CYCLEru
dc.typearticleru
dc.rights.licenseCC BY 4.0ru
dc.identifier.DOI10.29235/1561-2430-2022-58-2-155-168-
dc.description.alternativeIn this paper, we study the computational complexity for a problem of partitioning the edge set of a bipartite graph into the minimal number of subgraphs isomorphic to those of a simple cycle of order 4 in special graph classes. This problem is NP-hard and finds application in organizing the distribution of network packets over communication channels in the process of transmission from one router to another. We develop an O(nlogn) algorithm for solving that problem in a class of n order trees. Intractable cases of the problem are identified.ru
dc.identifier.scopus85135262077-
Располагается в коллекциях:Статьи факультета прикладной математики и информатики

Полный текст документа:
Файл Описание РазмерФормат 
640-1302-1-SM.pdf841,98 kBAdobe PDFОткрыть
Показать базовое описание документа Статистика Google Scholar



Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.