Název: Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů
Překlad názvu: Computational complexity of combinatorial problems in specific graph classes
Autoři: Masařík, Tomáš ; Fiala, Jiří (vedoucí práce)
Typ dokumentu: Rigorózní práce
Rok: 2016
Jazyk: cze
Abstrakt: [cze] [eng]
Tato diplomová práce se zabývá hranovou značkovatelností grafu v závislosti na parametrech p, q a λ. Pro parametry p = 2 a q = 1 jsme dokázali dichotomii. Tedy, že problém λ′ (2,1)-značkovatelnosti grafu je polynomiální pro λ ≤ 4 a NP- úplný pro λ > 4. Hranice NP-úplnosti se tedy posouvá o jedna oproti vrcholové variantě problému, λ(p,q)-značkovatelnosti grafu, která byla již vyřešena dříve. Pro polynomiální případy získáme poměrně snadnou charakterizaci pomocí kruž- nic a cest rozšířených o několik dalších vrcholů. K NP-převodu využíváme jeden z poměrně klasických NP-úplných problémů Monotónní všude různý 3-SAT. Celý důkaz převodu je rozdělen na čtyři části, neboť kromě rozlišení sudých a li- chých λ, bylo třeba vyvořit ještě speciální převody pro λ = 5 i λ = 6. 1 The topic of this diploma thesis is the edge distance labeling problem with specified parametres p, q and λ. We found a dychotomy for p = 2 and q = 1. So the problem is polynomial if λ ≤ 4 and it is NP-complete for λ > 4. The boundary is shifted by one prior to the vertex distance labeling problem, which has already been solved. Polynomial cases are characterized as some special paths and cycles with a few additional vertices. To show NP-completeness we use a well-known NP-complete problem of Monotone not all equal 3-SAT. That section has four parts: One for odd λ, one for even λ and two more reductions for λ = 5 and λ = 6. 1
Klíčová slova: kombinatorika; line-grafy; výpočetní složitost; značkovatelnost; combinatorics; computational complexity; labeling; line graphs

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/74574

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-343922


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Rigorózní práce