Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Properties of greedy trees
Thesis (MSc)--Stellenbosch University, 2014.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2015
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613955097100288 |
|---|---|
| access_status_str | Open Access |
| author | Razanajatovo Misanantenaina, Valisoa |
| author2 | Wagner, Stephan |
| author_browse | Razanajatovo Misanantenaina, Valisoa Wagner, Stephan |
| author_facet | Wagner, Stephan Razanajatovo Misanantenaina, Valisoa |
| author_sort | Razanajatovo Misanantenaina, Valisoa |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2014. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/95909 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:44:21.913Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2015 |
| publishDateRange | 2015 |
| publishDateSort | 2015 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/95909 Properties of greedy trees Razanajatovo Misanantenaina, Valisoa Wagner, Stephan Stellenbosch University. Faculty of Science. Department of Mathematical Sciences. Algorithms Greedy trees Majorization (Mathematics) UCTD Dissertations -- Mathematics Theses -- Mathematics Trees (Graph theory) Thesis (MSc)--Stellenbosch University, 2014. ENGLISH ABSTRACT: A greedy tree is constructed from a given degree sequence using a simple greedy algorithm that assigns the highest degree to the root, the second, the third, . . . , -highest degree to the root’s neighbours, etc. This particular tree is the solution to numerous extremal problems among all trees with given degree sequence. In this thesis, we collect results for some distancebased graph invariants, the number of subtrees and the spectral radius in which greedy trees play a major role. We show that greedy trees are extremal for the aforementioned graph invariants by means of two different approaches, one using level greedy trees and majorization, while the other one is somewhat more direct. Finally, we prove some new results on greedy trees for additive parameters with specific toll functions. AFRIKAANSE OPSOMMING: ’n Gulsige boom word vanuit ’n gegewe graadry deur middel van ’n eenvoudige gulsige algoritme gebou, wat die hoogste graad aan die wortel toewys, die tweede-, derde-, . . . , -hoogste graad aan die wortel se bure, ens. Hierdie spesifieke boom is die oplossing van ’n groot aantal ekstremale probleme onder al die bome met gegewe graadry. In hierdie tesis beskou ons ’n versameling van resultate oor afstand-gebaseerde grafiekinvariante, die aantal subbome en die spektraalstraal waarin gulsige bome ’n belangrike rol speel. Ons bewys dat gulsige bome ekstremaal vir die bogenoemde grafiekinvariante is deur van twee verskillende tegnieke gebruik te maak: een met behulp van vlak-gulsige bome en majorering, en ’n ander metode wat effens meer direk is. Laastens bewys ons sommige nuwe resultate oor gulsige bome vir additiewe parameters met spesifieke tolfunksies. 2015-01-13T11:48:19Z 2015-01-13T11:48:19Z 2014-12 Thesis http://hdl.handle.net/10019.1/95909 en_ZA Stellenbosch University application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Algorithms Greedy trees Majorization (Mathematics) UCTD Dissertations -- Mathematics Theses -- Mathematics Trees (Graph theory) Razanajatovo Misanantenaina, Valisoa Properties of greedy trees |
| title | Properties of greedy trees |
| title_full | Properties of greedy trees |
| title_fullStr | Properties of greedy trees |
| title_full_unstemmed | Properties of greedy trees |
| title_short | Properties of greedy trees |
| title_sort | properties of greedy trees |
| topic | Algorithms Greedy trees Majorization (Mathematics) UCTD Dissertations -- Mathematics Theses -- Mathematics Trees (Graph theory) |
| url | http://hdl.handle.net/10019.1/95909 |
| work_keys_str_mv | AT razanajatovomisanantenainavalisoa propertiesofgreedytrees |