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 MoĢ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.
Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:764953 |
Date | January 2018 |
Creators | Knapp, Christopher N. |
Contributors | Noble, S. ; Hall, R. |
Publisher | Brunel University |
Source Sets | Ethos UK |
Detected Language | English |
Type | Electronic Thesis or Dissertation |
Source | http://bura.brunel.ac.uk/handle/2438/15891 |
Page generated in 0.0017 seconds