تاکردن یک لینکیج درختی در کمترین طول ممکن

مسئله تا کردن لینکیج درختی به این صورت است که می خواهیم یک لینکیج که ساخترا درختی دارد را روی یک خط صاف در فضای یک بعدی طوری تا کنیم که به کمترین طول ممکن خود برسد تاکنون کارهایی در زمینه لینکیجهای ساده و تاکردن آنها در فضاهای با ابعاد مختلف انجام گرفته است ولی در زمینه تا نمودن لینکیج درختی الگوریتمی ارایه نشده است و این مسئله بعنوان یکی از مسائل NP-Complete محسوب میشود این مقاله برای تانمودن لینکیج درختی الگوریتمی شبه چند جمله ای با استفاده از روش برنامه نویسی پویا و الهام گرفت از روشهای استفاده شده برای تا نمودن لینکیج ساده ارایه می نماید. الگوریتم ارایه شده دارای پیچیدگی زمان O(L2nlog(n و حافظه O(nL می باشد