Original title: Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů
Translated title: Computational complexity of combinatorial problems in specific graph classes
Authors: Masařík, Tomáš ; Fiala, Jiří (advisor)
Document type: Rigorous theses
Year: 2016
Language: cze
Abstract: [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
Keywords: combinatorics; computational complexity; labeling; line graphs; kombinatorika; line-grafy; výpočetní složitost; značkovatelnost

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/74574

Permalink: http://www.nusl.cz/ntk/nusl-439137


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Rigorous theses