سال انتشار: ۱۳۸۴

محل انتشار: یازدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۸

نویسنده(ها):

میثم توسلی – دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف
فرشاد رستم آبادی – دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف
محمد قدسی – دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف

چکیده:

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