|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Optimal Two-Sided Embeddings of Complete Binary Trees in Rectangular Gridsстатья Перевод Исследовательская статья
Информация о цитировании статьи получена из
Scopus
Дата последнего поиска статьи во внешних источниках: 9 октября 2019 г.
- Авторы: Vysotskiy L.I., Lozhkin S.A.
- Журнал: Journal Computational Mathematics and Modeling
- Том: 30
- Номер: 2
- Год издания: 2019
- Первая страница: 115
- Последняя страница: 128
- DOI: 10.1007/s10598-019-09440-3
- Аннотация: The article considers the construction of optimal-area homeomorphic embeddings of complete binary trees in rectangular grids such that the leaf images are on the opposite sides of the grid and the edge images intersect only at node images. The minimum grid area that admits the embedding of a complete binary tree of depth n is shown to be asymptotically equal to (n/3)*2^n. An algorithm to construct an asymptotically optimal embedding of such a tree is proposed; the complexity of the algorithm is O(n*2^n) bit operations.
- Добавил в систему: Ложкин Сергей Андреевич