فهرس المقالات Network flows

• حرية الوصول المقاله
  • صفحة الملخص
  • نص كامل
  
  1 - مدل بندی مسأله هضم جزئی بصورت مساله شبکه جریان
  رضا ندیمی امید رنجبر
  نگاشت نقاط مرزی یکی از مسائل جالب توجه در زیست شناسی محاسباتی به شمار می‌رود. یک رشته DNA به صورت دنباله‌ای از حروف A, T, C, G می‌باشد. هنگامی که یک آنزیم محدود کننده به یک محلول DNA اضافه می‌شود، مولکول DNA از مکان‌های خاصی بریده می شود. هدف از نگاشت نقاط مرزی پیدا کرد أکثر

  نگاشت نقاط مرزی یکی از مسائل جالب توجه در زیست شناسی محاسباتی به شمار می‌رود. یک رشته DNA به صورت دنباله‌ای از حروف A, T, C, G می‌باشد. هنگامی که یک آنزیم محدود کننده به یک محلول DNA اضافه می‌شود، مولکول DNA از مکان‌های خاصی بریده می شود. هدف از نگاشت نقاط مرزی پیدا کردن نقاط برش برای یک آنزیم معین است. در روش هضم جزیی، برشها طوری انجام می‌شود که فاصله دو به دوی همه نقاط برش حاصل شود. در بیان ریاضی مساله، فاصله دو به دوی n نقطه واقع بر یک پاره خط داده شده است و هدف بدست آوردن خود این نقاط است. در بیوانفورماتیک این مساله به مساله هضم جزیی معروف شده است. در این مقاله یک مدل شبکه جریان تعمیم یافته برای مساله ارایه می‌دهیم. با توجه به اینکه کلاس پیچیدگی این مساله یکی از قدیمی‌ترین و مهمترین مسایل باز در بیوانفورماتیک نظری است(تاکنون نه الگوریتمی با زمان چند جمله ای و نه اثباتی بر Np-complete بودن آن ارایه شده است)، کاهش مساله هضم جزیی به مساله شبکه جریان دریچه جدیدی را برای چالش با این مساله می‌گشاید. تفاصيل المقالة
• حرية الوصول المقاله
  • صفحة الملخص
  • نص كامل
  
  2 - حل مسئله معکوس ماکزیمم جریان در شبکه پویا تحتفاصله همینگ تجمعی وزندار
  هاجر بنی خادمی حسن صالحی فتح آبادی
  معکوس ماکزیمم جریان پویا یکی از مهمترین مسائل شبکه های جریان میباشد که در تحقیقات پیشین، تحت معیار فاصلهاقلیدسی مورد بررسی قرار گرفته است. اما اخیراً مطالعات گستردهای در زمینه مسائل معکوس در شبکه های ایستا تحت معیارهمینگ، که ناشی از کاربردهای عملی آن است، انجام گرفته اس أکثر

  معکوس ماکزیمم جریان پویا یکی از مهمترین مسائل شبکه های جریان میباشد که در تحقیقات پیشین، تحت معیار فاصلهاقلیدسی مورد بررسی قرار گرفته است. اما اخیراً مطالعات گستردهای در زمینه مسائل معکوس در شبکه های ایستا تحت معیارهمینگ، که ناشی از کاربردهای عملی آن است، انجام گرفته است. لذا در این مقاله معکوس ماکزیمم جریان را در شبکه پویاتحت معیار همینگ مورد بررسی قرار میدهیم. برای جریان داده شده در شبکه پویا، میخواهیم با کمترین تغییرات ممکن دربردار ظرفیت کمانها، جریان داده شده، ماکزیمم جریان در شبکه باشد. بکارگیری فاصله همینگ بدلیل کاربردهای عملی آندر مواقعی که در آن تنها تعداد کمانهایی که ظرفیتشان تغییر میکند بدون در نظر گرفتن بزرگی تغییرات، برایمان اهمیتدارد. لذا در این مقاله بعد از اثبات نتایج اولیه، یک مسئله کمترین برش پویا برای حل معکوس ماکزیمم جریان ارائه شدهاست. همچنین الگوریتم بر مبنای بهینه سازی ترکیبیاتی برای حل مسئله معکوس در زمان چندجملهای ارائه شده است و درنهایت الگوریتم پیشنهادی روی یک شبکه نمونه پیاده سازی شده است. تفاصيل المقالة