برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: شبکه جریان داده‌شده که دارای ظرفیت (به انگلیسی: capacity) از گره u تا گره v است که به صورت داده‌شده، دارای منبع (به انگلیسی: s (source و چاهک (به انگلیسی: t (sink است. می‌خواهیم بیشترین میزان جریان را که می‌شود درون شبکه از s به t فرستاد را بیابیم. دو نوع عملیات روی گره‌ها انجام می‌شود: push و relabel. به‌طور کلی داریم:. جریان از u به v. ظرفیت قابل‌استفاده برابر است با.. تنها در صورتی از u به v عمل push را انجام می‌دهیم که. به ازای همه مقادیر u مقدار یک عدد صحیح غیر منفی است.. حاصل جمع جریان وارد شده و خارج‌شده از u. بعد از هر گام الگوریتم، جریان یک پیش جریان (به انگلیسی: preflow) است که شرایط زیر را دارد:. جریان بین و از ظرفیت بیشتر نباشد.. جریان شبکه را در هر دو جهت حفظ می‌کنیم. به ازای تمام گره‌ها به صورت،. تنها منبع امکان ایجاد جریان داشته باشد. توجه داشته باشید که آخرین وضعیت یک پیش‌جریان از وضعیت متناظر برای یک جریان مجاز در یک در یک شبکه جریان منظم، مجزاست. ملاحظه می‌کنیم که طولانی‌ترین مسیر ممکن از s به t دارای بزرگی گره است. بنابراین باید امکان. پذیر باشد که ارتفاع (به انگلیسی: height) را به گره‌های هر جریان مجاز اختصاص دهیم، و، و اگر یک جریان مثبت از u به v وجود داشت،. حال که ما ارتفاع گره‌ها را تعیین کردیم، جریان در شبکه به حرکت در می‌آید (مانند جریان آب بر روی پستی و بلندی). بر خلاف الگوریتم‌هایی مانند فورد-فالکرسون، جریان در طول شبکه، لزما یک جریان مجاز در اجرای الگوریتم نیست. به‌طور خلاصه، ارتفاع‌های گره‌ها (به جز s و t) تعیین شده‌اند، و جریان بین گره‌ها فرستاده می‌شود، تا زمانی که تمام جریان‌های ممکن به t برسند. سپس می‌توانیم افزایش ارتفاع گره‌های درونی را ادامه دهیم تا تمام جریان‌هایی که درون شبکه رفته‌اند ولی به t نرسیده‌اند، به سمت s بازگردند. یک گره قبل از پایان کار می‌تواند به ارتفاع برسد، بنا بر این، طولانی‌ترین مسیر ممکن که به s بر می‌گردد ولی شامل t نیست دارای طول است و. ارتفاع t روی صفر نگه داشته می‌شود. یک push از u به v به معنی فرستادن قسمتی از جریان اضافی ورودی به u به سمت v است. برای رخ دادن یک push باید سه شرط رعایت شود:. جریان ورودی به گره، از جریانی که تاکنون از آن خارج می‌شده بیشتر باشد.. ظرفیت قابل‌استفاده از u به v.. تنها امکان ارسال به گره در …
برداشت:
الگوریتم ارسال-برچسب (به انگلیسی : push–relabel algorithm) یکی از کارآمدترین الگوریتم‌ها برای محاسبهٔ یک مسئله بیشینه جریان است . الگوریتم عمومی دارای پیچیدگی زمانی است ، در حالی که پیاده‌سازی آن با قانون شیوهٔ رأس‌ها به صورت fifo دارای زمان اجرای ، با شیوهٔ انتخاب فعال‌ترین رأس دارای پیچیدگی زمانی و با پیاده‌سازی با کمک داده‌ساختار درخت پویای ترجان و اسلیتور دارای زمان اجرای است . مجانبا این الگوریتم ، از الگوریتم ادموند-کارپ که زمان اجرای آن است کاراتر است .