پیوندهای مفید
آمار
| تعداد نشریات | 7 |
| تعداد شماره‌ها | 399 |
| تعداد مقالات | 5,389 |
| تعداد مشاهده مقاله | 5,288,012 |
| تعداد دریافت فایل اصل مقاله | 4,882,748 |
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 | ||
| مراجع | ||
|
[1] S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, J. Algorithms, 12 (1991), p. 308–340.
[2] B. Courcelle, Graph rewriting: An algebraic and logic approach, in Formal Models and Semantics, Elsevier, 1990, pp. 193–242.
[3] , The monadic second-order logic of graphs. i. recognizable sets of finite graphs, Information and compu[1]tation, 85 (1990), pp. 12–75.
[4] M. Csur˝ os, J. A. Holey, and I. B. Rogozin ¨ , In search of lost introns, Bioinformatics, 23 (2007), pp. i87– i96.
[5] R. G. Downey and M. R. Fellows, Parameterized complexity, Springer Science & Business Media, 2012.
[6] S. El-Basil, Caterpillar (gutman) trees in chemical graph theory, Advances in the theory of Benzenoid hydrocarbons, (1990), pp. 273–289.
[7] H. B. Enderton, A mathematical introduction to logic, Elsevier, 2001.
[8] P. Hlinenˇ y, S.-i. Oum, D. Seese, and G. Gottlob ` , Width parameters beyond tree-width and their applcations, The computer journal, 51 (2008), pp. 326–362.
[9] M. Khosravani, Searching for optimal caterpillars in general and bounded treewidth graphs, PhD thesis, ResearchSpace, Auckland, 2011.
[10] A. Lozano, R. Y. Pinter, O. Rokhlenko, G. Valiente, and M. Ziv-Ukelson, Seeded tree alignment, IEEE/ACM transactions on Computational Biology and Bioinformatics, 5 (2008), pp. 503–513.
[11] M. Numan, A. Nawaz, A. Aslam, and S. I. Butt, Hosoya polynomial for subdivided caterpillar graphs, Combinatorial Chemistry & High Throughput Screening, 25 (2022), pp. 554–559.
[12] J. Tan and L. Zhang, The consecutive ones submatrix problem for sparse matrices, Algorithmica, 48 (2007), pp. 287–299. | ||
|
آمار تعداد مشاهده مقاله: 497 تعداد دریافت فایل اصل مقاله: 345 |
||