TY - JOUR
ID - 4907
TI - Breaking intractability of spanning caterpillar tree problem: A logical approach
JO - AUT Journal of Mathematics and Computing
JA - AJMC
LA - en
SN - 2783-2449
AU - Khosravani, Masoud
AD - Algoreen Software Ltd. Auckland, New Zealand
Y1 - 2022
PY - 2022
VL - 3
IS - 2
SP - 147
EP - 151
KW - Caterpillar Trees
KW - Monadic Second Order Logic
KW - optimization
KW - Parametrized Complexity
DO - 10.22060/ajmc.2022.21716.1104
N2 - 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].
UR - https://ajmc.aut.ac.ir/article_4907.html
L1 - https://ajmc.aut.ac.ir/article_4907_c0906e6f5060ef12191f8b5b4b7f51f7.pdf
ER -