Geodesic
Minimum linear arrangement of the transitive oriented, bipartite graphs
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2012), pp. 50-54 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{UZERU_2012_2_a7,
     author = {H. E. Sargsyan and S. Y. Markosyan},
     title = {Minimum linear arrangement of the transitive oriented, bipartite graphs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {50--54},
     year = {2012},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2012_2_a7/}
}
TY  - JOUR
AU  - H. E. Sargsyan
AU  - S. Y. Markosyan
TI  - Minimum linear arrangement of the transitive oriented, bipartite graphs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2012
SP  - 50
EP  - 54
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZERU_2012_2_a7/
LA  - en
ID  - UZERU_2012_2_a7
ER  - 
%0 Journal Article
%A H. E. Sargsyan
%A S. Y. Markosyan
%T Minimum linear arrangement of the transitive oriented, bipartite graphs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2012
%P 50-54
%N 2
%U http://geodesic.mathdoc.fr/item/UZERU_2012_2_a7/
%G en
%F UZERU_2012_2_a7
H. E. Sargsyan; S. Y. Markosyan. Minimum linear arrangement of the transitive oriented, bipartite graphs. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2012), pp. 50-54. http://geodesic.mathdoc.fr/item/UZERU_2012_2_a7/

[1] S. Even, Y. Shiloah, NP-Completeness of Several Arrangement Problems, Technical Report 43. Dept. of Computer Science, Technion, Israel, Haifa, 1975

[2] F.R.K. Chung, Labelings of Graphs, Academic Press, San Diego, 1988, 151–168 | MR

[3] D. Adolphson, T.C. Hu, “Optimal linear ordering”, SIAM J. Appl. Mathem., 25:3 (1973), 403–423 | DOI | MR | Zbl

[4] L.H. Harper, “Optimal Assignments of Numbers to Vertices”, SIAM J. Appl. Mathem., 12:1 (1964), 131–135 | DOI | MR | Zbl

[5] D.O. Muradyan, T.E. Piliposyan, “Minimal Numberings of a Rectangular Lattice”, Izv. Akad. Nauk Arm. SSR, 1:70 (1980), 21–27 (in Russian) | MR

[6] J. Cohen, F. Fomin, “Optimal Linear Arrangement of Interval Graphs”, 31st International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 2006, 267–279 | DOI | MR | Zbl