Publication Details:
Լույս է տեսնում 1948 թվականից՝ տարին 4 անգամ։
Journal or Publication Title:
Date of publication:
Volume:
Number:
ISSN:
Official URL:
Additional Information:
Հարությունյան Ա. Գ., Խաչատրյան Ռ. Ն., Арутюнян А. Г., Хачатрян Р. Н.
Title:
Coarse-Grained Parallelization Of The Spanning Graph Construction Algorithm
Other title:
Կմախքային գրաֆի կառուցման ալգորիթամի խոշորահատիկ զուգահեռացումը ; Крупнозернистая параллелизация алгоритма построения каркасного графа
Creator:
Harutyunyan, A.G. ; Khachatryan, R. N.
Contributor(s):
Պատ․ խմբ․՝ Ա․ Գ․ Նազարով (1957-1964) ; Մ․ Վ․ Կասյան (1964-1988) ; Ռ․ Մ․ Մարտիրոսյան (1989-2017 ) ; Գլխավոր խմբ․՝ Վ․ Շ․ Մելիքյան (2018-)
Subject:
Automataion And Control Systems
Uncontrolled Keywords:
minimum spanning tree ; rectilinear distance ; parallelization ; coarsegrainedparallelization ; VLSI Design ; Sweep-line algorithm
Coverage:
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:
Type:
Format:
Call number:
Digitization:
ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան