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