@article {
author = {Khosravani, Masoud},
title = {Breaking intractability of spanning caterpillar tree problem: A logical approach},
journal = {AUT Journal of Mathematics and Computing},
volume = {3},
number = {2},
pages = {147-151},
year = {2022},
publisher = {Amirkabir University of Technology},
issn = {2783-2449},
eissn = {2783-2287},
doi = {10.22060/ajmc.2022.21716.1104},
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].},
keywords = {Caterpillar Trees,Monadic Second Order Logic,optimization,Parametrized Complexity},
url = {https://ajmc.aut.ac.ir/article_4907.html},
eprint = {https://ajmc.aut.ac.ir/article_4907_a3190e25f6b882514c4b49e7f87e26d0.pdf}
}