Minimum 0-Extensions of Graph Metrics
| Název práce v češtině: | Minimum 0-Extension problém na grafových metrikách |
|---|---|
| Název v anglickém jazyce: | Minimum 0-Extensions of Graph Metrics |
| Klíčová slova: | splňování omezujících podmínek|nemodulární grafy|grafové metriky|výpočetní složitost |
| Klíčová slova anglicky: | constraint satisfaction|non-modular graphs|graph metrics|computational complexity |
| Akademický rok vypsání: | 2019/2020 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | RNDr. Jakub Bulín, Ph.D. |
| Řešitel: | Mgr. Martin Dvořák - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 10.01.2020 |
| Datum zadání: | 10.01.2020 |
| Datum potvrzení stud. oddělením: | 20.01.2020 |
| Datum a čas obhajoby: | 04.02.2021 09:00 |
| Datum odevzdání elektronické podoby: | 06.01.2021 |
| Datum odevzdání tištěné podoby: | 06.01.2021 |
| Datum proběhlé obhajoby: | 04.02.2021 |
| Oponenti: | Mgr. Vladan Majerech, Dr. |
| Zásady pro vypracování |
| The Minimum 0-Extension Problem [3] is an interesting subclass of binary CSP based on graph metrics. The aim of this thesis is to generalize the problem to graphs with arbitrary positive weights and analyze computational complexity of its threshold decision variant (with respect to the distance function of the graph).
The main goal is to determine whether the proof of NP-hardness of the Minimum 0-Extension Problem for simple graphs [3] can be extended to any non-modular graph (in the weighted sense). The secondary goal of the thesis is to determine which special cases of the problem can be solved or approximated efficiently, e.g. by linear programming relaxation techniques inspired by [1] or [3]. |
| Seznam odborné literatury |
| [1] G. B. Dantzig, D. R. Fulkerson, On the max-flow min-cut theorem of networks, in Linear Inequalities, Annals of Mathematics Studies 38 (1956) 215–221.
[2] E. Dalhaus, D. S. Johnson, C. Papadimitriou, P. Seymour, and M. Yannakakis, The complexity of the multiterminal cuts, SIAM Journal on Computing 23(4) (1994) 864–894. [3] A. V. Karzanov, Minimum 0-extensions of graph metrics, European Journal of Combinatorics 19(1) (1998) 71–101. |
| Předběžná náplň práce |
| Constraint Satisfaction Programming (CSP) is an important area of Artificial Intelligence frequently used in planning, scheduling, and game playing. We will study an interesting subclass of binary CSP based on graph metrics, called the “Minimum 0-extension problem”. We will generalize the problem from simple graphs to weighted graphs. The generalized problem is equivalent to the "Multifacility location problem", which has natural applications in economics. |