تخطي إلى التنقل الرئيسي تخطي إلى البحث تخطي إلى المحتوى الرئيسي

INVESTIGATIONS ON FINDING AND UPDATING SPANNING TREES IN PARALLEL.

المشروع: RESEARCH PROJECT

تفاصيل المشروع

Description

Fast parallel algorithms are presented for finding and updating the minimum-depth spanning trees of graphs. The computational model used is a parallel random access machine that allows simultaneous access to the same memory location during both read and write operations. The parallel minimum-depth spanning tree algorithm is based on a partial spanning tree doubling technique which is also found to be useful in updating the minimum-depth spanning tree when a new node or edge is added to the graph. The parallel minimum-depth spanning tree algorithm runs in O(log n log log n) time with O(n2⌈n/loglog n⌉) processors. The most notable results are O(loglog n) time parallel algorithms for updating the minimum-depth spanning tree solution when a new node (edge) is added to an n node graph whose minimum-depth spanning tree is known.

الحالةمنتهي
تاريخ البدء/النهاية الساري15/02/93 → 1/07/94

بصمة

استكشف موضوعات البحث التي تناولها هذا المشروع. يتم إنشاء هذه الملصقات بناءً على الجوائز/المنح الأساسية. فهما يشكلان معًا بصمة فريدة.