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

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

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

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

امید خوانساری نیا – دانشکده مهندسی کامپیوتر، دانشگاه صنعتی شریف
محمد قدسی – دانشکده مهندسی کامپیوتر، دانشگاه صنعتی شریف

چکیده:

این مقاله به مساله انتشار درکمترین زمان در شبکه های با مدل ارتباط تلفنی می پردازد. پس از بیان صورت مساله و مرور بر الگوریتمهای تقریبی که تاکنون طراحی شده اند، یک الگوریتم تقریبی جدید ارائه میگردد که جواب حاصل از آن نسبت به جواب بهینه، حداکثر به میزان O(Ön) بیشتر می باشد. ویژگی این الگوریتم، استفاده از تکنیک یافتن شاره بیشینه می باشد که رهیافتی جدید در مقایسه با روشهای بکار رفته درالگوریتمهای تقریبی موجود است. در نهایت نیز مقایسه ای بین الگوریتم جدید و بهترین الگوریتم موجود انجام میشود.