Trees and graph packing

Vásárhelyi Bálint Márk
Trees and graph packing.
Doktori értekezés, Szegedi Tudományegyetem (2000-).
(2018) (Kéziratban)

[thumbnail of Disszertacio.pdf]
Előnézet
PDF (disszertáció)
Download (1MB) | Előnézet
[thumbnail of Thesis-book.pdf]
Előnézet
PDF (tézisfüzet)
Download (340kB) | Előnézet
[thumbnail of tezisfuzet_nyilatkozattal.pdf]
Előnézet
PDF (tézisfüzet)
Download (355kB) | Előnézet
[thumbnail of publication_list.pdf] PDF (kapcsolódó saját publikációk)
Restricted to Csak az archívum karbantartója

Download (1MB)

Magyar nyelvű absztrakt

Ebben a disszertációban két fő témát vizsgálunk, mégpedig a szuffixfákat és gráfpakolási kérdéseket. A 2. fejezetben a szuffixfákkal foglalkozunk. A fejezet fő eredménye az egyszerű szuffixfák méretére adott alsó korlát. A további részekben pakolási feladatokat vizsgálunk. A 3. fejezetben majdnem szigorú feltételeket adunk egy páros pakolási feladatra. A 4. fejezetben egy fokszámsorozatokkal kapcsolatos beágyazási problémával foglalkozunk. Az 5. fejezetben megmutatjuk, hogy léteznek olyan korlátos fokú páros gráfok, melyeknek szeparáló halmaza kicsi, miközben sávszélessége nagy, és megmutatjuk, hogy bizonyos feltételek mellett ezeket a gráfokat be lehet ágyazni olyan gráfokba, melyek minimális foka kicsit nagyobb n/2-nél.

Absztrakt (kivonat) idegen nyelven

In this thesis we investigate two main topics, namely, suffix trees and graph packing problems. In Chapter 2, we present the suffix trees. The main result of this chapter is a lower bound on the size of simple suffix trees. In the rest of the thesis we deal with packing problems. In Chapter 3 we give almost tight conditions on a bipartite packing problem. In Chapter 4 we consider an embedding problem regarding degree sequences. In Chapter 5 we show the existence of bounded degree bipartite graphs with a small separator and large bandwidth and we prove that under certain conditions these graphs can be embedded into graphs with minimum degree slightly over n/2.

Mű típusa: Disszertáció (Doktori értekezés)
Publikációban használt név: Vásárhelyi Bálint Márk
Magyar cím: Fák és gráfpakolások
Témavezető(k):
Témavezető neve
Beosztás, tudományos fokozat, intézmény
MTMT szerző azonosító
Csaba Béla
egyetemi docens, PhD, habil., SZTE TTIK Bolyai Intézet
10019078
Szakterület: 01. Természettudományok > 01.01. Matematika
Doktori iskola: Matematika Doktori Iskola > Matematika- és Számítástudományok Doktori Iskola (1993-2021)
Tudományterület / tudományág: Természettudományok > Matematika- és számítástudományok
Nyelv: angol
Védés dátuma: 2018. december 04.
Kulcsszavak: suffix tree; graph packing
EPrint azonosító (ID): 9833
A mű MTMT azonosítója: 30618370
doi: https://doi.org/10.14232/phd.9833
A feltöltés ideje: 2018. máj. 28. 13:33
Utolsó módosítás: 2022. okt. 13. 15:29
Raktári szám: B 6456
URI: https://doktori.bibl.u-szeged.hu/id/eprint/9833
Védés állapota: védett

Actions (login required)

Tétel nézet Tétel nézet

Letöltések

Letöltések havi bontásban az elmúlt egy évben