مروری نظام مند بر روش های حل مسیله افزار گراف

مسیله افزار گراف (بخشبندی) یکی از بزرگ ترین و مهمترین مسایل در زمینه ی بهینه سازی و تیوری گراف می باشد که در بسیاری از زمینه های علمی مورد مطالعه و بررسی قرار گرفته است. از جمله این کاربردها می توان به مدارات VLSI، زمانبندی در سیستم های چند پردازنده ای، خوشه بندی، شبکه، پردازش تصویر، زیست شناسی، محاسبات جغرافیایی نام برد. به طور کلی این مسیله در رده مسایل NP قرار می گیرد. از جمله روش هایی که برای حل این مسیله می توان نام برد روش های دقیق، روش های اکتشافی، روش های هندسی می باشد. از آنجایی که مقاله جامعی که این مطالب را دربر بگیرد، ما در این مقاله به مرور و بررسی اینگونه روش ها برای حل مسیله بخبندی گراف و همچنین ابزارهایی که برای آن وجود دارد می پردازیم.

Keywords:

حل مسیله بخشنبدی گراف , الگوریتم های اکتشافی , الگوریتم های فراابتکاری , الگوریتم های هندسی , ابزارهای بخشبندی گراف