Open Access Te Herenga Waka-Victoria University of Wellington
Browse
thesis_access.pdf (664.05 kB)

Recognition Problems for Connectivity Functions

Download (664.05 kB)
thesis
posted on 2021-11-15, 13:37 authored by Jowett, Susan

A 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-01

Date of Award

2015-01-01

Publisher

Te Herenga Waka—Victoria University of Wellington

Rights License

Author Retains Copyright

Degree Discipline

Mathematics

Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Degree Level

Masters

Degree Name

Master of Science

ANZSRC Type Of Activity code

970101 Expanding Knowledge in the Mathematical Sciences

Victoria University of Wellington Item Type

Awarded Research Masters Thesis

Language

en_NZ

Victoria University of Wellington School

School of Mathematics, Statistics and Operations Research

Advisors

Whittle, Geoff