%0 Journal Article
%T Breaking intractability of spanning caterpillar tree problem: A logical approach
%J AUT Journal of Mathematics and Computing
%I Amirkabir University of Technology
%Z 2783-2449
%A Khosravani, Masoud
%D 2022
%\ 09/01/2022
%V 3
%N 2
%P 147-151
%! Breaking intractability of spanning caterpillar tree problem: A logical approach
%K Caterpillar Trees
%K Monadic Second Order Logic
%K optimization
%K Parametrized Complexity
%R 10.22060/ajmc.2022.21716.1104
%X 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].
%U https://ajmc.aut.ac.ir/article_4907_c0906e6f5060ef12191f8b5b4b7f51f7.pdf