انجمن کامپیوتر ایران

مسأله دسترس¬پذيري براي گراف G=(V,E)، به بررسي وجود يا عدم وجود مسير بين دو رأس داده شده مي¬پردازد. اين مسأله در حوزه¬هايي مانند زيست فناوري، وب معنايي، شبکه¬هاي کامپيوتري و شبکه¬هاي اجتماعي که داده¬هاي بسيار بزرگي را با ساختار گراف دارا مي¬باشند، نقش مهمي ايفا مي¬کند. همچنين اهميت و کاربرد اين مسأله در مديريت و الگوريتم¬هاي گراف بسيار قابل توجه است. در اين مقاله يک روش برچسب¬گذاري جديد براي گراف¬هاي جهت¬دار بزرگ ارائه شده است که مي¬تواند به شيوه¬اي بسيار کارا برچسب¬گذاري را انجام داده و به پرس¬وجوهاي دسترس¬پذيري در مرتبه‌اي از زمان ثابت تا زمان خطي پاسخ دهد. ويژگي مهم ديگر روش پيشنهادي اين است که اطلاعات دسترس¬پذيري تنها با يک بار پيمايش عمقي گراف محاسبه و بدون به کار گيري ساختار داده اضافي، به شيوه موثري ذخيره مي¬شوند. کارايي روش پيشنهادي نيز به وسيله آزمايشاتي مورد تحليل و ارزيابي قرار گرفته است. نتايج به دست آمده از اين روش، بهبودي را در زمان برچسب¬گذاري و اندازه برچسب¬ در مقايسه با روش GRAIL، که تنها ساختار شاخص مقياس¬پذير براي پاسخ به پرس¬وجوهاي دسترس¬پذيري است، نشان مي¬دهد.