Polyhedral study of the connected subgraph problem

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