Geodesic
Optimal level placement of the transitive oriented and bipartite oriented graphs by height
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2009), pp. 43-46.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this work we discuss level placement (numeration, arrangement) by height optimal algorithms for transitive oriented and bipartite oriented graphs. There are described three definitions of the oriented graph, and for those three definitions it is solved the level placement problem for transitive oriented graph. The problem of level placement of bipartite oriented graph is solved by the linear complexity algorithm, whereas the problems of level placement of transitive oriented graph are solved by the quadratic complexity algorithms.
Keywords: transitive oriented graph, level placement. 
@article{UZERU_2009_2_a7,
     author = {S. Y. Markosyan and A. H. Khachaturyan},
     title = {Optimal level placement of the transitive oriented and bipartite oriented graphs by height},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {43--46},
     publisher = {mathdoc},
     number = {2},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2009_2_a7/}
}
TY  - JOUR
AU  - S. Y. Markosyan
AU  - A. H. Khachaturyan
TI  - Optimal level placement of the transitive oriented and bipartite oriented graphs by height
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2009
SP  - 43
EP  - 46
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2009_2_a7/
LA  - en
ID  - UZERU_2009_2_a7
ER  - 
%0 Journal Article
%A S. Y. Markosyan
%A A. H. Khachaturyan
%T Optimal level placement of the transitive oriented and bipartite oriented graphs by height
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2009
%P 43-46
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2009_2_a7/
%G en
%F UZERU_2009_2_a7
S. Y. Markosyan; A. H. Khachaturyan. Optimal level placement of the transitive oriented and bipartite oriented graphs by height. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2009), pp. 43-46. http://geodesic.mathdoc.fr/item/UZERU_2009_2_a7/

[1] M.R. Garey, R.L. Graham, D.S. Johnson, D.E. Knuth, “Complexity results for bandwidth minimization”, SIAM J. Appl. Math., 34 (1978), 477–495. | DOI | MR | Zbl

[2] M.R Garey., D.S. Johnson, L. Stockmeyer, “Some simplified NP-complete graph problems”, Theor. Comput. Sci., 1 (1976), 237–267 | DOI | MR | Zbl

[3] Ch.H. Papadimitriou, “The NP-Completeness of the bandwidth minimization problem”, Computing, 16 (1976), 263–270 | DOI | MR | Zbl

[4] A.V Petrosyan, S.E. Markosyan, Yu.G. Shukuryan, Mathematical Problems of Automation and Projection of Calculating-Machine, Yer., 1977 (in Russian)

[5] G.G. Geoletsyan, “Flat placement of the vertices of tree with minimization of width”, DAN Arm. SSR, 56:4 (1973), 202–207 (in Russian)

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