مروری بر روش های حل مسئله بخش بندی گراف

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

کلیدواژه ها:

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