Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/15891
Title: | The complexity of greedoid Tutte polynomials |
Authors: | Knapp, Christopher N. |
Advisors: | Noble, S Hall, R |
Keywords: | Rooted graphs;Rooted digraphs;Binary greedoids;Algorithm;Matroids |
Issue Date: | 2018 |
Publisher: | Brunel University London |
Abstract: | We consider the computational complexity of evaluating the Tutte polynomial of three particular classes of greedoid, namely rooted graphs, rooted digraphs and binary greedoids. Furthermore we construct polynomial-time algorithms to evaluate the Tutte polynomial of these classes of greedoid when they’re of bounded tree-width. We also construct a Möbius function formulation for the characteristic polynomial of a rooted graph and determine the computational complexity of computing the coefficients of the Tutte polynomial of a rooted graph. |
Description: | This thesis was submitted for the award of Doctor of Philosophy and was awarded by Brunel University London |
URI: | http://bura.brunel.ac.uk/handle/2438/15891 |
Appears in Collections: | Dept of Mathematics Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
FulltextThesis.pdf | 738.63 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.