Հրապարակման մանրամասներ:

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

Ամսագրի կամ հրապարակման վերնագիր:

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

Հրապարակման ամսաթիվ:

2025

Հատոր:

78

Համար:

1

ISSN:

0002-306X

Պաշտոնական URL:

Լրացուցիչ տեղեկություն:

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

Այլ վերնագիր:

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

Աջակից(ներ):

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

Ծածկույթ:

121-128

Ամփոփում:

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.

Հրատարակության վայրը:

Երևան

Հրատարակիչ:

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

Ձևաչափ:

pdf

Նույնացուցիչ:

oai:arar.sci.am:427647

Դասիչ:

АЖ 413

Թվայնացում:

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

Բնօրինակի գտնվելու վայրը:

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