Souvislé řezy
| Název práce v češtině: | Souvislé řezy |
|---|---|
| Název v anglickém jazyce: | Connected Cuts |
| Klíčová slova: | teorie grafů|aproximační algoritmy|řezy|lineární programování|heuristiky |
| Klíčová slova anglicky: | graph theory|approximation algorithms|cuts|linear programming|heuristics |
| Akademický rok vypsání: | 2024/2025 |
| Typ práce: | diplomová práce |
| Jazyk práce: | |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. Mgr. Petr Kolman, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 21.10.2024 |
| Datum zadání: | 21.10.2024 |
| Datum potvrzení stud. oddělením: | 22.10.2024 |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| 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. |