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

Publish Year: 1384
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 1,207

This Paper With 8 Page And PDF Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

این Paper در بخشهای موضوعی زیر دسته بندی شده است:

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

ACCSI11_001

تاریخ نمایه سازی: 5 آذر 1390

Abstract:

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

Authors

میثم توسلی

دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف

فرشاد رستم آبادی

دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف

محمد قدسی

دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف

مراجع و منابع این Paper:

لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :
  • الگوریتم روی این داده‌ها، با تعداد پردازنده‌ی مختلف سعی کردیم ...
  • Pankaj K. Agarwal, Marc van Kreveld, and Subhash Suri Label ...
  • M. Formann and F. Wagner, A packing problem with applications ...
  • L. Kucera, K. Mehlhorn, B. Preis, and E. S chwarzenecker, ...
  • F. Wagner and A. Wolff., An efficient and effective approximation ...
  • Sh. Daneshpajouh, M. Ghodsi, Parallel Algorithm for Map Labeling Problem, ...
  • Map labeling and its generalization, In Proceedings of the ...
  • th ACM-SIAM Sympos on Discrete Algorithms, 1997, 148-157. ...
  • Sheung-Hung Poon, Chan-Su Shin, Tycho Strijk, and Alexander Wol Labeling ...
  • F. Rostamabadi and M. Ghodsi, Unit Height k-Position Map Labeling, ...
  • H. Imai and Ta. Asano, Finding the connected components and ...
  • R. J. Fowler, M. S. Paterson, and S. L. Tanimoto, ...
  • Behrooz Parhami, Introduction to Parallel Processing, Plenum Press 1999. ...
  • TH Cormen, CE Leiserson, RL Rivest, C Stein, Introduction to ...
  • نمایش کامل مراجع