GRAPH MATROID AND ANALYSIS OF SLEEPING TREES IN A GRAPH
DOI:
https://doi.org/10.30890/2567-5273.2025-40-02-036Keywords:
graph, matroid, spanning tree, Kruskal’s algorithm, graphic matroid, independent sets, combinatorial optimizationAbstract
This study explores the graphic matroid as a formal framework for modeling the construction of spanning trees in undirected graphs. By interpreting acyclic edge subsets as independent sets, the matroid structure provides a rigorous foundation for analyzinReferences
Matoya, K., & Oki, T. (2020). Pfaffian pairs and parities: Counting on linear matroid intersection and parity problems. https://arxiv.org/abs/1912.00620
Oxley, J.G. (2006) Matroid Theory. Oxford: Oxford University Press. Available at: Oxford Academic (Accessed: 13 August 2025). https://academic.oup.com/book/34846
Wahlström, M. (2024). Representative set statements for delta-matroids and the Mader pp. 780–810. SIAM. Advance online publication. Available at: https://doi.org/10.1137/1.9781611977912
Koana, T. and Wahlström, M. (2025). Faster Algorithms on Linear Delta-Matroids. In: O. Beyersdorf, M. Pilipczuk, E. Pimentel, and N.K. Thắng, eds. 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics, vol. 327, article no. 62, pp. 62:1–62:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. Available at: https://drops.dagstuhl.de/storage/00lipics/lipics-vol327-stacs2025/LIPIcs.STACS.2025.62/LIPIcs.STACS.2025.62.pdf
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Available at: Internet Archive (Accessed: 13 August 2025). https://archive.org/details/introduction-to-algorithms-third-edition-2009
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
