الگوریتم Goldberg و Tarjan
مکاشفه ای > برچسب‌گذاری مجدد کردن

سومین کشف مهم عملیات برچسب‌گذاری مجدد را گسترش می‌دهد به‌طوری‌که رأس‌ها ی زیادی در یک مرحله برچسب‌گذاری مجدد می‌شوند. اگر S یک زیرمجموعه از راس‌هایی باشد که شامل همهٔ رأس‌های بیش از حد منفی باشد، متمم  v(g)/sحداقل یک راس فعال داردو فرض کنید که در گراف مورد قبول از V (G) / S به  Sلبه هم نداریم سپس عملیات برچسب‌گذاری مجدد قابل اجرا است:پتانسیل همهٔ راس‌ها در V (G) / S  را می‌توان به اندازه ɛ کاهش داد.
مشخص است که این عملیات بهینگی ɛ را در f از بین نمی‌برد. این نظریه که در محدوده اعداد push  و عملیات برچسب‌گذاری مجدد است،اگر عملیات برچسب‌گذاری مجدد به کار برده شوند ، تغییر نمی‌کنند و تعداد دفعات ان هم اهمیتی ندارد.(در مثال [2] اثبات شده‌است)
عملیات برچسب‌گذاری مجدد (set_relabel) می‌تواند این‌گونه بازگو شود:
{\text{begin}}
procedure relabel global(π)
begin
S := { v∊ V (G) : ef (v) < 0};
while V (G) \ S contains an active vertex do
begin
Add all vertices to S from which S can be reached in G f;
if V (G) \ S contains an active vertex then
π(v) := π (v) -  ɛ for all v ∊V (G) \ S;
end;
end;
این روش می‌تواند به صورت کارامدی توسط ساختار سطلی (bucket structure) انجام شود. سطل‌ها با اعداد صحیح نامنفی نشان داده می‌شوند. اولین  سطل به شماره B(v) به هر راس v اختصاص داده می‌شود برای اینکه سطل حاوی v یا ∞را (در صورتی‌که v در هیچ‌کدام از سطل‌ها قرار نگرفته باشد) نشان دهد.
در نهایت B(v) شماره عملیات برچسب‌گذاری مجدد خواهد شد که برای راس v به کار برده می‌شود.
ابتدا همهٔ رأس‌ها ی منفی در سطل با مقدار صفر قرار می‌گیرند و بقیه سطل‌ها خالی می‌مانند. سپس سطل‌ها به این شکل بررسی می‌شوند:
برای هر سطل i، به‌طوری‌که i=1,2,….  و هر راس v  به صورت B(v) = i و هر لبهٔ  e=(w,v)به عنوان عضوی از Gf ، راس w از B(w) حذف می‌شود.
اگر k بزرگترین  سطل نشان دهنده راس فعال باشد، پتانسیل هر راس v اندازه ɛ کم می‌شودmin(B(v), k).
اگر این بعد از هر n بار عملیات عادی برچسب‌گذاری مجدد استفاده شود، بدترین حالت زمان اجرای بهبود بخشیدن تغییر نمی‌کند. تعداد عملیات برچسب‌گذاری مجدد (همان عدد k)  در طول برچسب‌گذاری مجدد کلی( (relabel global برابر O(n) است. بنابراین تعداد کل عملیات برچسب‌گذاری مجدد در طول بهبود بخشیدن O(n2) است.
ادعا می‌کنند که هر گره که درGoldberg [6] و GoldbergO(n) سهیم می‌شود، در هر مرحله بهبود بخشی برچسب‌گذاری مجدد می‌شود. هر چند که این، زمانی می‌تواند درست باشد که فقط در هر مرحله بهبود بخشی به اندازه O(n)، برچسب‌گذاری مجدد داشته باشیم. چون در هر برچسب‌گذاری مجدد، راس‌های منزوی شرکت دارند.
به‌طور تجربی، کشف برچسب‌گذاری مجدد ، تعداد عملیات را کاهش می‌دهد . کار اضافه برای روش
برچسب‌گذاری مجددکلی قابل توجه است. اما در اکثر مواقع زمان اجرای کل کاهش می یابد.
5)نتایج تجربی
نتایجی روی IBMRS/6000Mod .550 workstations. به دست آمده‌است ، با دو ویژگی سر وکار داریم:
اولین گروه توسط NETGEN تولید می‌شوند٫ابزاریست که توسط Klingmanو Napier توسعه داده شده‌است. ابتدا یک مولد، منبعی را تولید می‌کند و سپس یک شبکه یدک شامل لبه‌های با ظرفیت بالا را می‌سازد برای اینکه از امکان ان اطمینان حاصل شود. سپس لبه هارا به صورت رندم اضافه می‌کند. گروه شامل 35 شبکه  با 200 تا 8000 راس است.
دومین گروه شامل مشکلات ناشی از فاز دادن در طرح VLSI است. این شبکه ها خیلی پراکنده‌اند. تعداد لبه‌ها فقط 2-3برابر تعداد رأس‌ها است. گروه شامل 570 شبکه است. تعداد رأس‌ها بین 10 تا 1000 است.
چون تفاوت‌های ناچیزی در نتایج محاسبه شده بین دو کلاس داریم، باید خودمان را به حالت دوم محدود کنیم چون حالت اول مشکلات بیشتری دارد.
محاسبه اولیه در الگوریتم Goldberg و Tarjan در اکثر مواقع کمتر از %1 از زمان اجرای کل است.
اجرای این اکتشاف‌ها برای اینکه الگوریتم Goldberg-Tarjan رقابتی شوند بسیار مفید است. با این کشفیات کوتاه‌ترین مسیر الگوریتم موفق به دست می اید. به هر حال ما باید بیان کنیم که نمونه‌هایی هم داریم که از مسیرهای کوتاه الگوریتم  Goldberg-Tarjan  بهتر است.
هر اکتشافی پیشرفت قابل توجهی از تعداد عملیات برچسب‌گذاری مجدد و pushرا می‌دهد و زمان اجرا به وضوح به این عملیات‌ها بستگی دارد.
کشف push-look-ahead اثر قابل توجهی روی تعداد عملیات push دارد:وقتی در الگوریتم پایه این تعداد تقریباً دوبرابرتعداد عملیات برچسب‌گذاری مجدد است، فرکانس هر دو عملیات  هنگام استفاده از push-look-ahead برابر می‌شود.
استفاده زیاد از برچسب‌گذاری مجدد می‌تواند زمان اجرا را برای اعداد بزرگ کاهش دهد (n> 1000).
برچسب‌گذاری مجدد  از بقیه کم اهمیت تر است اما مواردی هست که با عدم استفاده از هر یک از کشفیات می‌توان زمان اجرا را بسیار بالاتر برد.