Necessary Conditions for Optimal Permissible Placement by the Height of the Transitive Directed Tree with One Root
Keywords:
transitive directed graph, optimal placementAbstract
In the graph theory the problem of the minimum placement of graph by the height, which is similarly formulated in [2] (the problem of minimum cut arrangement of graph), is known. The problem is NP-complete [3]. In the present paper a partial case of this problem, i.e. the problem of optimal permissible placement by the height of the transitive directed tree with one root (which is a such transitive directed graph, the arc base of which forms a directed tree with one root), is formulated. In this paper some new concepts are introduced and necessary conditions for optimal solving of the new formulated problem are given.
References
A. H. Khachaturyan, “The optimal permissible placement by the height of the transitiveoriented tree containing one vertex of branching”, Mathematical Problems of ComputerScience, vol. 33, pp183-186, 2010.
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 InformationSciences 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 forbandwidth minimization”, SIAM J. Appl. Math., vol. 34, pp. 477–495. 1978.
M. R. Garey, D. S. Johnson and L. Stockmeyer, “Some simplified NP-complete graphproblems”, Theor. Comput. Sci., vol. 1, pp. 237–267. 1976.
Ch. H. Papadimitriou, “The NP-completeness of the bandwidth minimization problem”,Computing, v. 16, pp. 263–270. 1976.
A.V. Petrosyan, S. E. Markosyan, Yu. H. Shukuryan, Mathematical Problems ofAutomation and Projection of Calculating-Machine. Yer., (in Russian). 1977.
G.G. Geoletsyan, “Flat placement of the vertices of tree with minimization of width”, DANArm. 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,” TechnicalReport, Physico-Technical Institute of Low Temperatures, Academy of Sciences of UkraineSSR, 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.
