Algoritmy pro řezy v grafech

• Thesis title in Czech: Algoritmy pro řezy v grafech
• Thesis title in English: Algorithms for cuts in graphs
• Key words: Řezy v grafech, Spektralní teorie, Řídké řezy, Expanze
• English key words: Graph partitioning, Spectral theory, Sparse cuts, Expansion, Conductance
• Academic year of topic announcement: 2011/2012
• Thesis type: diploma thesis
• Thesis language: angličtina
• 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: 04.01.2012
• Date of assignment: 04.01.2012
• Confirmed by Study dept. on: 11.01.2012
• Date and time of defence: 20.01.2014 09:00
• Date of electronic submission: 05.12.2013
• Date of submission of printed version: 06.12.2013
• Date of proceeded defence: 20.01.2014
• Opponents: doc. Hans Raj Tiwary, M.Sc., Ph.D.

Guidelines

Řezy v grafech patří mezi základní problémy kombinatorické optimalizace.
Techniky pro hledání "malých" řezů slouží jako nástroj pro mnoho algoritmů typu
Rozděl a panuj. Úkolem diplomanta bude vypracovat přehled o hlavních
algoritmech pro hledání "malých" řezů (např. zmínit techniky nafukování
balónku, vnořování metrických prostorů, semidefinitni relaxaci, převod na
problém maximálního toku, spektrální alg.), některé z nich implementovat (s
použitím vhodných knihoven) a porovnat. Hlavní pozornost bude věnována tzv.
"řídkým" řezům a jejich souvislosti s grafovou expanzí.

References

Knihy:
David P. Williamson a David B. Shmoys: The Design of Approximation
Algorithms, Cambridge University Press, 2011.

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, a A. Schrijver:
Combinatorial Optimization, 1998, John Wiley and Sons, New York.

Jiří Matoušek: Thirty-three Miniatures: Mathematical and Algorithmic
Applications of Linear Algebra, 2010, American Mathematical Society.


Články:
Kevin J. Lang, Michael W. Mahoney, and Lorenzo Orecchia. 2009. Empirical
Evaluation of Graph Partitioning Using Spectral Embeddings and Flow. In
Proceedings of the 8th International Symposium on Experimental Algorithms (SEA
'09), Jan Vahrenhold (Ed.). Springer-Verlag, Berlin, Heidelberg, 197-208.
DOI=10.1007/978-3-642-02011-7_19 http://dx.doi.org/10.1007/978-3-642-02011-7_19

Rohit Khandekar, Satish Rao, and Umesh Vazirani. 2006. Graph partitioning using
single commodity flows. In Proceedings of the thirty-eighth annual ACM
symposium on Theory of computing (STOC '06). ACM, New York, NY, USA, 385-390.
DOI=10.1145/1132516.1132574

Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, and Nisheeth K.
Vishnoi. 2008. On partitioning graphs via single commodity flows. In
Proceedings of the 40th annual ACM symposium on Theory of computing (STOC '08).
ACM, New York, NY, USA, 461-470. DOI=10.1145/1374376.1374442
http://doi.acm.org/10.1145/1374376.1374442

Web:
10th DIMACS Implementation Challenge - Graph Partitioning and Graph Clustering
http://www.cc.gatech.edu/dimacs10/index.shtml