Return to search

The complexity of greedoid Tutte polynomials

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.

Identiferoai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:764953
Date January 2018
CreatorsKnapp, Christopher N.
ContributorsNoble, S. ; Hall, R.
PublisherBrunel University
Source SetsEthos UK
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation
Sourcehttp://bura.brunel.ac.uk/handle/2438/15891

Page generated in 0.0021 seconds