تعبیه ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم
Publish Year: 1398
Type: Journal paper
Language: Persian
View: 104
This Paper With 7 Page And PDF Format Ready To Download
- Certificate
- I'm the author of the paper
Export:
Document National Code:
JR_AICTI-2-4_001
Index date: 20 December 2023
تعبیه ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم abstract
دراین مقاله در نظر داریم تا یک درخت با N گره را روی N نقطه داخل یک چند ضلعی با n راس تعبیه کنیم این تعبیه باید به گونه ای باشد که تعداد خم های درخت حاصل حداقل شود. ایده ی اصلی الگوریتم جدید مدل کردن مسئله به صورت مسئله ی تطبیق دهی گراف ها واستفاده از الگوریتم های
تطبیق دهی گراف است که منجر به بررسی مسئله ی فاصله ی پیوندی و مسیر با حداقل تعداد لینک می شود، سپس با به کار بردن مفهوم تصحیح خطا ویافتن یک تابع هزینه ی مناسب و استفاده از روش تجزیه ی گراف ها، تطبیق دهی گراف ها را با حداقل هزینه برای به حداقل رساندن تعداد خم انجام می-دهیم و الگوریتم دارای پیچیدگی محاسباتی O(N۲n+N۴)است.
تعبیه ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم Keywords:
تعبیه ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم authors
علیرضا باقری
دانشگاه صنعتی امیرکبیر