Breaking intractability of spanning caterpillar tree problem: A logical approach
Author(s):
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:
In this paper we pursue a logical approach to prove that the optimisation problem of finding a spanning caterpillar tree in a graph has polynomial algorithm for bounded tree width graphs. A caterpillar (tree) is a tree with the property that if one removes all its leaves only a path is left. To this end we use Courcelle's theorem and we show how one can present the spanning caterpillar tree problem by using monadic-second order logical expression. The value of this approach reflected better by the fact that finding a spanning caterpillar in a graph is an NP-complete problem [9].
Language:
English
Published:
AUT Journal of Mathematics and Computing, Volume:3 Issue: 2, Oct 2022
Pages:
147 to 151
magiran.com/p2481830
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!