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.0016 seconds