Souvislost a resilience grafů
| Thesis title in Czech: | Souvislost a resilience grafů |
|---|---|
| Thesis title in English: | Graph connectivity and resilience |
| Key words: | graf, podgraf, souvislost, resilience, kostry |
| English key words: | graph, subgraph, connectivity, resilience, spanning trees |
| Academic year of topic announcement: | 2014/2015 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | RNDr. Ondřej Pangrác, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 18.01.2015 |
| Date of assignment: | 26.01.2015 |
| Confirmed by Study dept. on: | 29.01.2015 |
| Date and time of defence: | 15.09.2015 09:00 |
| Date of electronic submission: | 30.07.2015 |
| Date of submission of printed version: | 31.07.2015 |
| Date of proceeded defence: | 15.09.2015 |
| Opponents: | doc. Mgr. Robert Šámal, Ph.D. |
| Guidelines |
| Student se v práci bude zabývat problémy resilience a resilientního směrování v grafech. Tyto otázky jsou blízké souvislosti grafů. Jde o nalezení přechodových funkcí ve vrcholech grafu, které následně umožňují, po odebrání nějaké podmnožiny hran, dosažení cílového vrcholu bez dalšího prozkoumávání struktury grafu.
Metody pro řešení problému mohou zahrnovat využití vlastností k-souvislých grafů, hledání disjunktních koster a koster s omezenými průniky apod.. Student should study problems related to the resilience of graphs and resilient routings. The topic is closely related to the graph connectivity. The goal is to a mappings on the edges incident with each vertex whose enable to a given target vertex after removing a subset of edges of restricted size. Techniques used to reach a solution can exploit properties of k-connected graphs, finding disjoint spanning trees of a graph and spanning trees with restricted intersections. |
| References |
| W. T. Tutte: On the problem of decomposing a graph into n connected factors (1961)
A. Frank: On disjoint trees and arborescences (1978) S. Fujishige: A note on disjoint arborescences (2010) C. Király: Algorithms for finding a rooted (k,1)-edge-connected orientation (2013) |
| Preliminary scope of work |
| Student se v práci bude zabývat problémy resilience a resilientního směrování v grafech. Tyto otázky jsou blízké souvislosti grafů. Jde o nalezení přechodových funkcí ve vrcholech grafu, které následně umožňují, po odebrání nějaké podmnožiny hran, dosažení cílového vrcholu bez dalšího prozkoumávání struktury grafu. |
| Preliminary scope of work in English |
| Student should study problems related to the resilience of graphs and resilient routings. The topic is closely related to the graph connectivity. The goal is to a mappings on the edges incident with each vertex whose enable to a given target vertex after removing a subset of edges of restricted size. |