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

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

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

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

حسین صالحی فتح آبادی – دانشکده ریاضی، آمار و علوم کامپیوتر دانشگاه تهران
علی ابراهیم نژاد –
سید مهدی منصور زاده –

چکیده:

در این مساله شبکه جریان با کمترین هزینه (G=(V,E بررسی می شود که روی کمانهای معین، میزان جریان یکسانی انتقال می یابد. نخست، الگوریتم سیمپلکس شبکه را به شیوه مناسبی برای حل مساله تعمیم می دهیم. در راستای این هدف، نشانمیدهیم که هر جواب پایه ای این مساله با یک درخت پوشا از کمانهای S=E-R یا با یک درخت دوگانه کامل از S وxR متناظر است. سپس، مساله شبکه جریان یکسان را بصورت مساله شبکه جریان با کمترین هزینه پارامتریک مدل بندی نموده که منجر به ارائه الگوریتم سیمپلکس پارامتریک می شود.