A simpler and faster algorithm to compute Induced Star Partitions in graphs
Resumo
An induced star partition of a graph is a partition of its vertex set in which all parts must induce a star, i.e., each part i must induce a subgraph isomorphic to a K1,ti for some ti ≥ 1. We present a new algorithm for computing one such partition, which improves on previous results in the literature, being both simpler and more efficient.
Referências
Babenko, M. and Gusakov, A. (2013). New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs. LIPIcs, Volume 9, STACS 2011, 9:519–530.
Blum, N. (1990). A new approach to maximum matching in general graphs. In Paterson, M. S., editor, Automata, Languages and Programming, volume 443, pages 586–597. Springer-Verlag, Berlin/Heidelberg.
Divya, D. and Vijayakumar, S. (2024). On Star Partition of Split Graphs. In Kalyanasundaram, S. and Maheshwari, A., editors, Algorithms and Discrete Applied Mathematics, volume 14508, pages 209–223. Springer Nature Switzerland, Cham.
Edmonds, J. (1965). Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467.
Gabow, H. N. and Tarjan, R. E. (1989). Faster Scaling Algorithms for Network Problems. SIAM Journal on Computing, 18(5):1013–1036.
Gallian, J. A. (2022). A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, 1000:DS6: Dec 2.
Kelmans, A. K. (1997). Optimal packing of induced stars in a graph. Discrete Mathematics, 173(1-3):97–127.
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48–50.
Lovász, L. and Plummer, M. D. (2009). Matching Theory, volume 367. American Mathematical Soc.
Manber, U. (1998). Introduction to algorithms: a creative approach. Addison-Wesley, Reading, Mass., reprinted with corr., [nachdr.] edition.
Micali, S. and Vazirani, V. V. (1980). An O(v|v| c |E|) algoithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), pages 17–27, Syracuse, NY, USA. IEEE.
Saito, A. and Watanbe, M. (1993). Partitioning Graphs into Induced Stars. Ars Combinatoria, Volume 036:3–6.
Shalu, M., Vijayakumar, S., Sandhya, T., and Mondal, J. (2022). Induced star partition of graphs. Discrete Applied Mathematics, 319:81–91.
Blum, N. (1990). A new approach to maximum matching in general graphs. In Paterson, M. S., editor, Automata, Languages and Programming, volume 443, pages 586–597. Springer-Verlag, Berlin/Heidelberg.
Divya, D. and Vijayakumar, S. (2024). On Star Partition of Split Graphs. In Kalyanasundaram, S. and Maheshwari, A., editors, Algorithms and Discrete Applied Mathematics, volume 14508, pages 209–223. Springer Nature Switzerland, Cham.
Edmonds, J. (1965). Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467.
Gabow, H. N. and Tarjan, R. E. (1989). Faster Scaling Algorithms for Network Problems. SIAM Journal on Computing, 18(5):1013–1036.
Gallian, J. A. (2022). A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, 1000:DS6: Dec 2.
Kelmans, A. K. (1997). Optimal packing of induced stars in a graph. Discrete Mathematics, 173(1-3):97–127.
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48–50.
Lovász, L. and Plummer, M. D. (2009). Matching Theory, volume 367. American Mathematical Soc.
Manber, U. (1998). Introduction to algorithms: a creative approach. Addison-Wesley, Reading, Mass., reprinted with corr., [nachdr.] edition.
Micali, S. and Vazirani, V. V. (1980). An O(v|v| c |E|) algoithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), pages 17–27, Syracuse, NY, USA. IEEE.
Saito, A. and Watanbe, M. (1993). Partitioning Graphs into Induced Stars. Ars Combinatoria, Volume 036:3–6.
Shalu, M., Vijayakumar, S., Sandhya, T., and Mondal, J. (2022). Induced star partition of graphs. Discrete Applied Mathematics, 319:81–91.
Publicado
20/07/2025
Como Citar
GOMES, Guilherme C. M.; PRATES, Matheus T..
A simpler and faster algorithm to compute Induced Star Partitions in graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 16-20.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.7517.
