Necessary Conditions for Optimal Permissible Placement by the height of the Transitive Directed Tree with One Root (part second)
Keywords:
transitive directed graph, optimal placementAbstract
The present paper is the second part of the paper [1]. Here we have introduced a couple of additional concepts and have obtained some additional necessary conditions for the solution of the problem formulated in paper [1].
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, “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.
