|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 2009, Issue 2, Pages 43–46
(Mi uzeru261)
|
|
|
|
Informatics
Optimal level placement of the transitive oriented and bipartite oriented graphs by height
S. Y. Markosyan, A. H. Khachaturyan Chair of Discrete Mathematics and Theoretical Informatics YSU, Armenia
Abstract:
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.
Received: 01.04.2009 Accepted: 30.04.2009
Citation:
S. Y. Markosyan, A. H. Khachaturyan, “Optimal level placement of the transitive oriented and bipartite oriented graphs by height”, Proceedings of the YSU, Physical and Mathematical Sciences, 2009, no. 2, 43–46
Linking options:
https://www.mathnet.ru/eng/uzeru261 https://www.mathnet.ru/eng/uzeru/y2009/i2/p43
|
Statistics & downloads: |
Abstract page: | 54 | Full-text PDF : | 18 | References: | 14 |
|