Souvislé řezy
| Thesis title in Czech: | Souvislé řezy |
|---|---|
| Thesis title in English: | Connected Cuts |
| Key words: | teorie grafů|aproximační algoritmy|řezy|lineární programování|heuristiky |
| English key words: | graph theory|approximation algorithms|cuts|linear programming|heuristics |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | diploma thesis |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. Mgr. Petr Kolman, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 21.10.2024 |
| Date of assignment: | 21.10.2024 |
| Confirmed by Study dept. on: | 22.10.2024 |
| Guidelines |
| Cut problems in graphs are fundamental problems in computer science that are important both in theory and in practice. There are many different versions of cut problems, depending on the constraints on the cut (separate a single pair of vertices, several pairs of vertices, every pair of vertices in a given set, or any pair of vertices in the graph, ...) and on the objective (minimize the total number of edges removed, maximize it, minimize the number of edges on the most connected component, ...). However, until recently, not much attention was given to cut problems with the extra requirement that the parts of the graph be connected (e.g., in MaxCut, the additional requirement is that there are exactly two connectivity components). The extra requirement that the parts of the graph be connected typically makes the problem harder.
The student will 1. prepare a survey of the relevant related results, including results on connected graph partitions; 2. compile a list of interesting connected cut problems, including both known and newly proposed problems; 3. attempt to design an algorithm for (approximately) solving some of the problems from the above list; and, optionally 4. conduct an experimental evaluation of your LP relaxations for some of the problems. |
| References |
| Textbooks:
R. K. Ahuja, T. L. Magnati, J. B. Orlin. Network Flows: Theory, Algorithms, and Applications, Pearson, 1993. A. Schrijver: Combinatorial Optimization - Polyhedra and Efficiency, Springer, 2003. Papers: Aissi, H., Mahjoub, A.R. On the minimum cut problem with budget constraints. Math. Program. 203, 421–442. 2024. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz. Min-Max Graph Partitioning and Small Set Expansion. SIAM J. Comput. 43(2): 872-904. 2014. Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits, and Ziena Zeif. Balanced Crown Decomposition for Connectivity Constraints. Proc. of 29th Annual European Symposium on Algorithms (ESA). LIPIcs Volume 204, pp. 26:1-26:15. 2021. Chen W., Samatova N. F., Stallmann M. F., W. Hendrix, and W. Ying. On size-constrained minimum s–t cut problems and size-constrained dense subgraph problems. Theoretical Computer Science, 609:434–442. 2016. Chen, Y., Chen, ZZ., Lin, G. et al. Approximation Algorithms for Maximally Balanced Connected Graph Partition. Algorithmica 83, 3715–3740. 2021. |