مسئله بیشترین جریان برای گرافهای بدست آمده از مشبکه بازی ریزش چیپ

در این مقاله گرافهایی را معرفی میکنیم کهs-t مسیرهای آن با رابطه طولانیترین مسیر، یک مشبکه القا میکنند. این گرافها را توسط مشبکه بازی ریزش چیپ میسازیم، بطوریکه-s-t مسیرهای آن توسط عناصر این مشبکه مرتب شده باشند. این مشبکه دارای خواص زیرمدولی و توالی است. بنابراین میتوان از این مشبکه در یک الگوریتم دوفازی حریصانه استفاده نمود و مسئله بیشترین جریان این گراف را حل کرد

کلیدواژه ها:

مسئله بیشترین جریانs-t مسیرها ، الگوریتم دوفازی حریصانه ، بازی ریزش چیپ ، مشبکه