MINIMUM LINEAR ARRANGEMENT OF THE TRANSITIVE ORIENTED, BIPARTITE GRAPHS

Authors

  • H.E. Sargsyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia
  • S.Ye. Markosyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2012.46.2.050

Keywords:

linear arrangement, transitive oriented graphs, NP-completeness

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.

Downloads

Published

2012-05-10

How to Cite

Sargsyan, H., & Markosyan, S. (2012). MINIMUM LINEAR ARRANGEMENT OF THE TRANSITIVE ORIENTED, BIPARTITE GRAPHS. Proceedings of the YSU A: Physical and Mathematical Sciences, 46(2 (228), 50–54. https://doi.org/10.46991/PYSU:A/2012.46.2.050

Issue

Section

Informatics