velikost textu

Computational and structural apects of interval graphs and their variants

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Computational and structural apects of interval graphs and their variants
Název v češtině:
Výpočetní a strukturální otázky intervalových grafů a jejich variant
Typ:
Diplomová práce
Autor:
Bc. Jana Novotná
Vedoucí:
prof. RNDr. Jan Kratochvíl, CSc.
Oponent:
RNDr. Vít Jelínek, Ph.D.
Id práce:
212504
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (N1801)
Obor studia:
Matematická lingvistika (IML)
Přidělovaný titul:
Mgr.
Datum obhajoby:
9. 9. 2019
Výsledek obhajoby:
Výborně
Jazyk práce:
Angličtina
Klíčová slova:
intervalový graf, jednotkový intervalový graf, výpočetní složitost, kliková šířka, největší řez
Klíčová slova v angličtině:
interval graph, unit interval graph, computational complexity, clique-width, maximum cut
Abstrakt:
Intervalové grafy, průnikové grafy úseček (intervalů) na reálné přímce, hrají klíčovou roli při studování algoritmů a specifických strukturálních vlastností. Velmi studovanou třídou jsou také jednotkové intervalové grafy, vlastní podtřída intervalových grafů, kde každý interval má jednotkovou délku. V práci se věnu- jeme smíšeným jednotkovým intervalovým grafům, grafům vzniklým zobecněním jednotkových intervalových grafů, kde každý interval má stále jednotkovou délku, ale může být různého typu (uzavřený, otevřený, polouzavřený). Tato drobná modi- fikace zahrnuje výrazně širší třídu grafů, například smíšené jednotkové intervalové grafy nejsou na rozdíl od jednotkových grafů spáruprosté. Heggernes, Meister a Papadopoulos přišli s bublinkovým modelem, takovou reprezentací jednotkových intervalových grafů, která se jeví užitečná při konstrukci různých algoritmů. Tento model rozšiřujeme na třídu smíšených intervalových grafů. Původní bublinkový model využili autoři Boyaci, Ekim a Shalom, kteří s jeho pomocí dokazovali, že problém největšího řezu v jednotkovém intervalovém grafu je polynomiální. V jejich důkazu jsme však objevili nejspíše neopravitelnou chybu. Dalším přínosem práce jsou ukázky využití našeho rozšířeného bublinkového mod- elu, na němž stavíme subexponenciální algoritmus pro problém největšího řezu na smíšených jednotkových intervalových grafech, který nám navíc dává pro specifické grafy polynomiální algoritmus, čímž rozšiřujeme do té doby známé polynomiální výsledky dokonce i pro jednotkové intervalové grafy. Dále s pomocí našeho modelu nacházíme lepší horní hranici klikové šířky smíšených jednotkových intervalových grafů. Kliková šířka je jedním z nejobecnějších grafových parametrů, kde řada problémů je řešitelná v dosažitelném čase, máme-li její efektivní reprezentaci. Bohužel spočtení přesné hodnoty a reprezentace klikové šířky je NP-těžké, tudíž dobré horní odhady, obzvlášť ty algoritmické, jsou užitečné.
Abstract v angličtině:
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs—a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, compared to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs. The original bubble model was used by Boyaci, Ekim, and Shalom for proving the polynomiality of the MaxCut problem on unit interval graphs. However, we found a significant mistake in the proof which seems to be hardly repairable. Moreover, we demonstrate advantages of such model by providing a subexponential-time algorithm solving the MaxCut problem on mixed unit interval graphs using our extended version of the bubble model. In addition, it gives us a polynomial-time algorithm for specific mixed unit interval graphs; that improves a state-of-the-art result even for unit interval graphs. We further provide a better algorithmic upper-bound on the clique-width of mixed unit interval graphs. Clique-width is one of the most general stuctural graph parameters, where a large group of natural problems is still solvable in the tracktable time when an efficient representation is given. Unfortunately, the exact computation of the clique-width representation is NP-hard. Therefore, good upper-bounds on the size of clique-width are highly appreciated, in particular, when such a bound is algoritmic.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Jana Novotná 858 kB
Stáhnout Abstrakt v českém jazyce Bc. Jana Novotná 22 kB
Stáhnout Abstrakt anglicky Bc. Jana Novotná 24 kB
Stáhnout Posudek vedoucího prof. RNDr. Jan Kratochvíl, CSc. 535 kB
Stáhnout Posudek oponenta RNDr. Vít Jelínek, Ph.D. 112 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Jan Hajič, Dr. 152 kB