thesis_access.pdf (664.05 kB)
Download fileRecognition Problems for Connectivity Functions
thesis
posted on 2021-11-15, 13:37 authored by Jowett, SusanA connectivity function is a symmetric, submodular set function. Connectivity functions arise naturally from graphs, matroids and other structures. This thesis focuses mainly on recognition problems for connectivity functions, that is when a connectivity function comes from a particular type of structure. In particular we give a method for identifying when a connectivity function comes from a graph, which uses no more than a polynomial number of evaluations of the connectivity function. We also give a proof that no such method can exist for matroids.
History
Copyright Date
2015-01-01Date of Award
2015-01-01Publisher
Te Herenga Waka—Victoria University of WellingtonRights License
Author Retains CopyrightDegree Discipline
MathematicsDegree Grantor
Te Herenga Waka—Victoria University of WellingtonDegree Level
MastersDegree Name
Master of ScienceANZSRC Type Of Activity code
970101 Expanding Knowledge in the Mathematical SciencesVictoria University of Wellington Item Type
Awarded Research Masters ThesisLanguage
en_NZVictoria University of Wellington School
School of Mathematics, Statistics and Operations ResearchAdvisors
Whittle, GeoffUsage metrics
Keywords
GraphConnectivity functionsMatroidsSchool: School of Mathematics, Statistics and Operations Research010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)970101 Expanding Knowledge in the Mathematical SciencesDegree Discipline: MathematicsDegree Level: MastersDegree Name: Master of ScienceCombinatorics and Discrete Mathematics (excl. Physical Combinatorics)