H. E. Sargsyan, S. Y. Markosyan, “Minimum linear arrangement of the transitive oriented, bipartite graphs”, Уч. записки ЕГУ, сер. Физика и Математика, 2012, выпуск 2,страницы 50

Эта публикация цитируется в 2 статьях

Informatics

Minimum linear arrangement of the transitive oriented, bipartite graphs

[Минимальная линейная нумерация двусторонних, транзитивно ориентированных графов, по длине]

H. E. Sargsyan, S. Y. Markosyan

Chair of Discrete Mathematics and Theoretical Informatics YSU, Armenia

Аннотация: Работа посвящена изучению проблемы минимальной линейной нумерации вершин графов (MINLA) в классе транзитивно ориентированных графов. В работе доказана $NP$-полнота MINLA для транзитивно ориентированных графов.

Ключевые слова: linear arrangement, transitive oriented graphs, $NP$-completeness.

Поступила в редакцию: 22.03.2012
Принята в печать: 06.06.2012

Язык публикации: английский