RUS  ENG
Full version
JOURNALS // Proceedings of the Yerevan State University, series Physical and Mathematical Sciences // Archive
Proceedings of the YSU, Physical and Mathematical Sciences, 2012 Issue 2, Pages 50–54 (Mi uzeru136)
This article is cited in 2 papers

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

Abstract: We study the minimum linear arrangement of the graphs (MINLA) on transitive oriented graphs. We prove that MINLA of transitive oriented graphs is $NP$-complete.

Keywords: linear arrangement, transitive oriented graphs, $NP$-completeness.

Received: 22.03.2012
Accepted: 06.06.2012

Language: English


© Steklov Math. Inst. of RAS, 2024