Optimal Permissible Placement by the Height of the Transitive Directed Tree with One Root
Keywords:
a transitive directed graph, an optimal placementAbstract
In paper [1] we have introduced a new concept – the transitive directed tree with one root and have formulated its minimum permissible placement problem by the height. In the papers [1] and [2] we have introduced a couple of new concepts and obtained necessary conditions for the solution of that problem. In the present paper using the results and the introduced concepts from the papers [1] and [2] we obtain an optimal polynomial algorithm for the problem solution and present the proof of its optimality.
References
A. H. Khachaturyan, “Necessary Conditions for Optimal Permissible Placement by the Height of the Transitive Directed Tree with One Root”, Mathematical Problems of Computer Science, vol. 36, pp. 104-114, 2012.
A. H. Khachaturyan, “Necessary Conditions for Optimal Permissible Placement by the Height of the Transitive Directed Tree with One Root (part second)”, Mathematical Problems of Computer Science, vol. 37, pp. 102-107, 2012.
A.H. Khachaturyan, “The optimal permissible placement by the height of the transitive oriented tree containing one vertex of branching”, Mathematical Problems of Computer Science, vol. 30, pp. 71-75, 2008.
M.R. Garey, D.S. Johnson, Computers and intractability: A guide to the theory of NPcompleteness. San Francisco, CA: W.H. Freeman, 1979.
F. Gavril, “Some NP-complete problems on graphs,” Proc.11th Conf. on Information Sciences and Systems, Johns Hopkins University, Baltimore, MD, pp. 91-95, 1977.
M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth, “Complexity results for bandwidth minimization”, SIAM J. Appl. Math., vol. 34, pp. 477–495. 1978.
M.R. Garey, D.S. Johnson and L. Stockmeyer, “Some simplified NP-complete graph problems”, Theor. Comput. Sci., vol. 1, pp. 237–267. 1976.
Ch.H. Papadimitriou, “The NP-copleteness of the bandwidth minimization problem”, Computing, v. 16, pp. 263–270. 1976.
A.V. Petrosyan, S.E. Markosyan, Yu.G. Shukuryan, Mathematical Problems of Automation and Projection of Calculating-Machine. Yer., (in Russian). 1977.
G.G. Geoletsyan, “Flat placement of the vertices of tree with minimization of width”, DAN Arm. SSR, issue 56, no. 4, pp. 202–207 (in Russian). 1973.
L. M. Goldberg and I. A. Klipker, “Minimum placement of trees on a line,” Technical Report, Physico-Technical Institute of Low Termeperatures, Academy of Sciences of Ukraina SSR, USSR. 1976.
Y. Shiloach, “A minimum linear arrangement algorithm for undirected trees” Report, Dept. Of Applied Mathematics, Weizmann Institute, Rehovot, Israel. 1976.
D. Adolphson and T.C. Hu, “Optimal linear ordering”, SIAM J. Appl. Math., vol. 25, no. 3, pp. 403–423. 1973.
C. Berge, The Theory of Graphs and Its Applications. New York: Wiley, 1962.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
