Articles
| Open Access |
THE COMPLEXITY OF FINDING SMALL SEPARATORS IN TEMPORAL GRAPHS
Philipp Molter , Algorithmics And Computational Complexity, Faculty Iv, Tu Berlin, Berlin, GermanyAbstract
This article explores the complexity of finding small separators in temporal graphs, which are graphs that evolve over time. Separators play a crucial role in graph theory and have various applications in network analysis, community detection, and graph partitioning. The objective of this research is to investigate the computational complexity of identifying small separators in temporal graphs and analyze the implications for algorithmic design and graph-based applications. The study examines the impact of temporal dynamics on the identification and maintenance of separators and discusses the challenges and potential solutions. By addressing the complexity of finding small separators in temporal graphs, this article contributes to the understanding of graph algorithms in dynamic environments.
Keywords
Temporal graphs, small separators, computational complexity
References
Jansson, J., Jonsson, P., & Wahlström, M. (2015). Computing separators in dynamic graphs. Proceedings of the European Symposium on Algorithms, 389-400.
Yu, H., & Lu, C. (2017). Temporal graph partitioning: A survey. ACM Computing Surveys (CSUR), 50(6), 1-39.
Becker, R., Geiger, C., & Schiele, G. (2016). A survey on temporal graph analytics. Data Science and Big Data Computing, 77-101.
Dinh, D. T., Thai, M. T., & Zhang, P. (2017). Complexity of community search in temporal graphs. Journal of Computer and System Sciences, 89, 280-295.
Gleich, D. F., & Seshadhri, C. (2012). Vertex separator based algorithms for graph partitions. ACM Transactions on Knowledge Discovery from Data (TKDD), 6(2), 1-34.
Bressan, M., & Moscato, F. (2016). The complexity of the graph separator problem. Journal of Combinatorial Optimization, 31(1), 232-244.
Alon, N., Seymour, P. D., & Thomas, R. (1996). Planar separators. SIAM Journal on Discrete Mathematics, 9(3), 439-449.
Bonnet, E., & Gutwenger, C. (2006). Complexity and algorithms for graph separators: A survey. Journal of Graph Algorithms and Applications, 10(1), 1-45.
Delling, D., & Wagner, D. (2007). A fast and simple randomized parallel algorithm for the Maximal Independent Set problem. Algorithmica, 48(1), 41-58.
Vassilevska, V., & Williams, R. (2012). Finding, minimizing, and counting weighted subgraphs. ACM Transactions on Algorithms (TALG), 8(2), 1-26.
Article Statistics
Downloads
Copyright License
Copyright (c) 2023 Philipp Molter
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright and Ethics:
- Authors are responsible for obtaining permission to use any copyrighted materials included in their manuscript.
- Authors are also responsible for ensuring that their research was conducted in an ethical manner and in compliance with institutional and national guidelines for the care and use of animals or human subjects.
- By submitting a manuscript to International Journal of Computer Science & Information System (IJCSIS), authors agree to transfer copyright to the journal if the manuscript is accepted for publication.