Trees and graph packing

Vásárhelyi Bálint Márk
Trees and graph packing.
PhD, University of Szeged.
(2018)

[img]
Preview
PDF (disszertáció)
Download (826kB) | Preview
[img]
Preview
PDF (címlap)
Download (19kB) | Preview
[img]
Preview
PDF (tézis)
Download (275kB) | Preview
[img]
Preview
PDF (tézis)
Download (228kB) | Preview
[img]
Preview
PDF (related own publications)
Download (1MB) | Preview

Abstract in Hungarian

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.

Abstract in foreign language

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.

Item Type: Thesis (PhD)
Creators: Vásárhelyi Bálint Márk
Hungarian title label: Fák és gráfpakolások
Title of the thesis in foreign language: Trees and graph packing
Divisions: Doctoral School of Mathematics
Discipline label: természettudományok > matematika- és számítástudományok
Defence date label: 2018. December 04.
Supervisor label:
SupervisorSupervisor scientific name labelEmail
Dr. Csaba Bélaegyetemi docens, PhD, habil., SZTE TTIK Bolyai Intézetbcsaba@math.u-szeged.hu
Reviewer label:
Reviewer name labelReviewer scientific name labelEmail
Dr. Erdős PéterDSc, tudományos tanácsadó, MTA Rényi Alfréd Matematikai Kutatóintézeterdos.peter@renyi.mta.hu
Dr. Ruszinkó MiklósDSc, tudományos tanácsadó, MTA Rényi Alfréd Matematikai Kutatóintézetruszinko.miklos@renyi.mta.hu
President label:
President name labelPresident scientific name labelEmail
Dr. Czédli GáborDSc, egyetemi tanár, SZTE TTIK Bolyai Intézetczedli@math.u-szeged.hu
Member label:
Member name labelMember scientific name labelEmail
Dr. Fodor FerencPhD, habilitált egyetemi docens, SZTE TTIK Bolyai Intézetfodorf@math.u-szeged.hu
Dr. Jordán TiborDSc, egyetemi tanár, ELTE TTK Matematikai Intézet, Operációkutatási Tanszékjordan@cs.elte.hu
Dr. Hajnal PéterPhD, habil, tanszékvezető egyetemi docens, SZTE TTIK Bolyai Intézethajnal@math.u-szeged.hu
Uncontrolled Keywords: suffix tree; graph packing
Item ID: 9833
Identification Number: 30618370
doi: https://doi.org/10.14232/phd.9833
Date Deposited: 2018. May. 28. 13:33
Last Modified: 2019. Apr. 02. 10:25
Depository no.: B 6456
Supervisor: Dr. Csaba Béla
Supervisor scientific name label: egyetemi docens, PhD, habil., SZTE TTIK Bolyai Intézet
URI: http://doktori.bibl.u-szeged.hu/id/eprint/9833
Defence/Citable status: Defended.

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year