The Optimal Permissible Placement by the Height of the Transitive Oriented Treecontaining One Vertex of Branching
Abstract
In this paper we consider the optimal permissible placement by the height of the following type of transitive oriented graphs (the height of the vertex is the number of the arcs passing through the vertex): the graph consists of chains of quantity s ≥ 2 branching after the end of the chain. The problem was solved by the algorithm of s log s complexity.
References
В. А. Евстигнеев, “Применение теории графов в программировании”,1985.
А. В. Петросян, С. Е. Маркосян, Ю. Г. Шукурян, “Математические вопросы автоматизации и проектирования ЭВМ”.Ереван, 1977.
Г. Г. Геолецян, “Плоское размещение вершин дерева на линии с минимизацией ширины.” ДАН Апм ССР, вып. 56, Но-4, стр.202-207, 1973
M.R. Garey, R.L. Graham, D.S. Johnson, and D.E. Knuth “Complexity results for bandwidth minimization”, SIAM J. Appl. Math. 34, pp. 477-495, 1978.
M.R. Garey, D.S. Johnson, and L. Stockmeyer “Some simplified NP-complete graph problems”, Theor. Comput. Sci.1, pp. 237-267, 1976.
Ch. H. Papadimitriou, “The NP-copleteness of the bandwidth minimization problem”, Computing 16, pp.263-270, 1976.
D. Adolphson, and T. C. Hu, “Optimal linear ordering”, SIAM J. Appl. Math., vol.25,No.3, pp. 403- 423, 1973.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
