Different perspectives on graph homomorphism problems
| Název práce v češtině: | Různé pohledy na problém grafového homomorfismu |
|---|---|
| Název v anglickém jazyce: | Different perspectives on graph homomorphism problems |
| Klíčová slova: | Graf|Homomorfismus grafů|Hamiltonovská cesta|Pokrytí cestami|Nezávislost grafu|Výpočetní složitost|Algoritmus|Signovaný graf|Grafové nakrytí|Půlhrany |
| Klíčová slova anglicky: | Graph|Graph homomorphism|Hamiltonian path|Path cover|Independence number|Computational complexity|Algorithm|Signed graph|Graph cover|Covering projection|Semi-edges |
| Akademický rok vypsání: | 2019/2020 |
| Typ práce: | disertační práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | prof. RNDr. Jan Kratochvíl, CSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 18.09.2019 |
| Datum zadání: | 18.09.2019 |
| Datum potvrzení stud. oddělením: | 04.10.2019 |
| Datum a čas obhajoby: | 30.06.2025 13:00 |
| Datum odevzdání elektronické podoby: | 21.01.2025 |
| Datum odevzdání tištěné podoby: | 23.01.2025 |
| Datum proběhlé obhajoby: | 30.06.2025 |
| Oponenti: | prof. Jérémie Chalopin |
| RNDr. Bernard Lidický, Ph.D. | |
| Zásady pro vypracování |
| The student will study available literature about geometric representations of graphs, identify plausible open problems and try to solve them, or at least provide progress in solving them. The possible topics will include but not be restricted to intersection and contact graphs of geometric objects, relation to graph drawing, studying the computational complexity of recognition, partial representation extension and simultaneous representation problems. |
| Seznam odborné literatury |
| Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN 9780133016154.
Scott, John (2000), "Sociograms and Graph Theory", Social network analysis: a handbook (2nd ed.), Sage, pp. 64–69, ISBN 9780761963394. McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, 2, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3 Proceedings of GD - Graph Drawing Symposia, SoCG - Symposia on Computational Geometry, EuroCG - European Workshop on Computational Geometry, and other relevant conferences Further publications in international journals and conference proceedings following recommendations of the advisor |
| Předběžná náplň práce |
| Geometrické reprezentace grafů jsou studovány hned ze dvou důvodů - jednak definují třídy grafů, které vycházejí z praktických aplikací, na druhé straně mnohé z těchto tříd mají strukturální charakterizace, které vedou k polynomiálním algoritmům pro úlohy, jež jsou jinak NP-těžké pro obecné grafy. Tato oblast je bohatým zdrojem otevřených problémů, některé z nichž jsou zřejmě obtížné a otevřené po dlouhou dobu, avšak o řešení či pokroku v řešení mnohých jiných je pravidelně referováno na mezinárodních konferencích. Toto téma nabízí příležitost rychle se zapojit do živého výzkumu, včetně mezinárodní spolupráce. |
| Předběžná náplň práce v anglickém jazyce |
| Geometric representations of graphs are studied for at least two reasons - first they define graph classes that arise from natural applications, and secondly, many of these graph classes allow structural characterizations that lead to polynomial-time algorithms for problems that are otherwise NP-hard for general graphs. The area is a rich source of open problems, some of them long-standing and challenging, but many of them are such that progress in solving them is regularly reported upon at annual international conferences. The topic offers possibility of quickly joining live research, including international collaboration. |