Algoritmy pro řezy v grafech
Název práce v češtině: | Algoritmy pro řezy v grafech |
---|---|
Název v anglickém jazyce: | Algorithms for cuts in graphs |
Klíčová slova: | Řezy v grafech, Spektralní teorie, Řídké řezy, Expanze |
Klíčová slova anglicky: | Graph partitioning, Spectral theory, Sparse cuts, Expansion, Conductance |
Akademický rok vypsání: | 2011/2012 |
Typ práce: | diplomová práce |
Jazyk práce: | angličtina |
Ú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í: | 04.01.2012 |
Datum zadání: | 04.01.2012 |
Datum potvrzení stud. oddělením: | 11.01.2012 |
Datum a čas obhajoby: | 20.01.2014 09:00 |
Datum odevzdání elektronické podoby: | 05.12.2013 |
Datum odevzdání tištěné podoby: | 06.12.2013 |
Datum proběhlé obhajoby: | 20.01.2014 |
Oponenti: | doc. Hans Raj Tiwary, M.Sc., Ph.D. |
Zásady pro vypracování |
Ř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í. |
Seznam odborné literatury |
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 |