Logo BSU

  1. Электронная библиотека БГУ
  2. Факультет прикладной математики и информатики
  3. НАУЧНЫЕ ПУБЛИКАЦИИ ФАКУЛЬТЕТА ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ
  4. Статьи факультета прикладной математики и информатики
Даты публикации Авторы Заглавия Темы
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ: https://elib.bsu.by/handle/123456789/344033
Полная запись метаданных
Поле DCЗначениеЯзык
dc.contributor.authorДугинов, О.И.-
dc.contributor.authorХимич, С.С.-
dc.date.accessioned2026-03-17T10:30:01Z-
dc.date.available2026-03-17T10:30:01Z-
dc.date.issued2022-
dc.identifier.citationВесці Нацыянальнай акадэміі навук Беларусі. Серыя фізіка-матэматычных навук.2022; Т. 58(2): С. 155-168.ru
dc.identifier.urihttps://elib.bsu.by/handle/123456789/344033-
dc.description.abstractИзучается вычислительная сложность задачи разбиения ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4, в специальных классах графов. Задача относится к числу NP-трудных и находит применение при организации распределения сетевых пакетов по каналам связи в процессе передачи от одного маршрутизатора к другому. Разработан алгоритм, решающий задачу в классе деревьев порядка <i>n</i> за время <i>O</i>(<i>n</i> log <i>n</i>). Выделены трудноразрешимые случаи задачи.ru
dc.language.isoruru
dc.publisherНациональная академия наук Беларусиru
dc.rightsinfo:eu-repo/semantics/openAccessru
dc.subjectЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетикаru
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 <i>O</i>(<i>n</i>log<i>n</i>) algorithm for solving that problem in a class of n order trees. Intractable cases of the problem are identified.ru
Располагается в коллекциях:Статьи факультета прикладной математики и информатики

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



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