الگوریتمی موازی برای برچسب گذاری نقشه ها به صورت تقریبی

دراین مقاله ابتدا به بررسی الگوریتم های تقریبی برای برچسب گذاری نقشه ها می پردازیم و سپس الگوریتم های موازی برای آن بیان میکنیم برچسب گذاری نقشه ها صورتهای مختلفی دارد که در اکثر موارد این مساله جز مسائل NP-Hard قرار میگیرد دراین مقاله پس از معرفی بعضی حالتهای مختلف این مساله ابتدا یک الگوریتم ترتیبی را که برای حالتی که برچسب ها ارتفاعی واحد دارند با زمان اجرای O(nlog n ضریب تقریبی برابر 2 دارد بیان می کنیم پس از آن حالت توسعه یافته همین الگورتی که با زمان اجرای O(nlogn+n2k-1 ضریب تقریبی 1+1/k را نتیجه می دهد بیان خواهیم کرد در ادامه دو الگوریتم موازی مختلف برای برچسب گذاری یکی در مدل CREW PRAM و دیگری برای مدل تولی ارائه میدهیم

کلیدواژه ها:

برچسب گذاری ، هندسه محاسباتی ، الگوریتم های موازی ، الگوریتم های تقریبی