Publication Details:

Լույս է տեսնում 1948 թվականից՝ տարին 4 անգամ։

Journal or Publication Title:

ՀՀ ԳԱԱ և ՀՊՃՀ Տեղեկագիր. Տեխնիկական գիտություններ =Proceedings of the NAS RA and SEUA: Technical Sciences

Date of publication:

2025

Volume:

78

Number:

1

ISSN:

0002-306X

Official URL:

Additional Information:

Հարությունյան Ա. Գ., Խաչատրյան Ռ. Ն., Арутюнян А. Г., Хачатрян Р. Н.

Other title:

Կմախքային գրաֆի կառուցման ալգորիթամի խոշորահատիկ զուգահեռացումը ; Крупнозернистая параллелизация алгоритма построения каркасного графа

Contributor(s):

Պատ․ խմբ․՝ Ա․ Գ․ Նազարով (1957-1964) ; Մ․ Վ․ Կասյան (1964-1988) ; Ռ․ Մ․ Մարտիրոսյան (1989-2017 ) ; Գլխավոր խմբ․՝ Վ․ Շ․ Մելիքյան (2018-)

Coverage:

121-128

Abstract:

The spanning graph construction problem is to create a sparse graph over a given set of points so that the graph contains at least one minimum spanning tree under a specified distance metric. This problem is the basis for many algorithms like rectilinear minimum spanning tree construction, efficient Steiner tree construction, obstacle aware Steiner tree construction, etc. These algorithms are used in many fields of computer science, especially in VLSI routing. As many of these algorithms are NP-complete problems and some of them use the spanning graph construction approach, parallelization of the spanning graph construction algorithm will optimize other problems as well. In this paper, we present the coarse-grained parallelization approach of the spanning graph construction algorithm. The proposed algorithm, compared to the existing sequential algorithm, achieves an average performance improvement of about 40-60% and keeps the correctness of the original algorithm.

Place of publishing:

Երևան

Publisher:

«Պոլիտեխնիկ» տպ.

Format:

pdf

Identifier:

oai:arar.sci.am:427647

Call number:

АЖ 413

Digitization:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան

Location of original object:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան