Breaking intractability of spanning caterpillar tree problem: A logical approach | ||
| AUT Journal of Mathematics and Computing | ||
| مقاله 3، دوره 3، شماره 2، آذر 2022، صفحه 147-151 اصل مقاله (330.19 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22060/ajmc.2022.21716.1104 | ||
| نویسنده | ||
| Masoud Khosravani* | ||
| Algoreen Software Ltd. Auckland, New Zealand | ||
| چکیده | ||
| 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]. | ||
| کلیدواژهها | ||
| Caterpillar trees؛ Monadic second order logic؛ Optimization؛ Parametrized complexity | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 734 تعداد دریافت فایل اصل مقاله: 781 |
||
| تعداد نشریات | 9 |
| تعداد شمارهها | 455 |
| تعداد مقالات | 5,771 |
| تعداد مشاهده مقاله | 8,375,062 |
| تعداد دریافت فایل اصل مقاله | 6,933,327 |