RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2021, номер 1, страницы 55–57 (Mi vmumm4379)

Краткие сообщения

О сложности линейной укладки нагруженных ориентированных ациклических графов

М. И. Щекалёв, Г. В. Боков, В. Б. Кудрявцев

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: В работе рассматриваются нагруженные ориентированные ациклические графы, ребрам которых приписаны веса — целые неотрицательные числа. Исследуется сложность линейной укладки вершин таких графов в порядке топологической сортировки. Получена точная оценка функции Шеннона сложности линейной укладки нагруженных ориентированных ациклических графов.

Ключевые слова: нагруженные ориентированные ациклические графы, линейная укладка, топологическая сортировка, сложность, функция Шеннона.

УДК: 510.52

Поступила в редакцию: 30.10.2019


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2021, 76:1, 35–36

Реферативные базы данных:


© МИАН, 2024