On the complexity of the representation of simplicial complexes by trees

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