Brunel University Research Archive (BURA) >
Research Areas >
Information Systems and Computing >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/818

Title: Evaluating the rank generating function of a graphic 2-polymatroid
Authors: Noble, SD
Keywords: Polymatroid
Rank generating function
Matroid
Computational complexity
#P-hard
Graph
Publication Date: 2006
Publisher: Cambridge University Press
Citation: Combinatorics, Probability and Computing 15: 449-461, May 2006
Abstract: We consider the complexity of the two-variable rank generating function, $S$, of a graphic 2-polymatroid. For a graph $G$, $S$ is the generating function for the number of subsets of edges of $G$ having a particular size and incident with a particular number of vertices of $G$. We show that for any $x,y \in \mathbb{Q}$ with $xy \not = 1$, it is $\#$P-hard to evaluate $S$ at $(x,y)$. We also consider the $k$-thickening of a graph and computing $S$ for the $k$-thickening of a graph.
URI: http://bura.brunel.ac.uk/handle/2438/818
ISSN: 0963-5483
Appears in Collections:Mathematics
Information Systems and Computing

Files in This Item:

File Description SizeFormat
polymatroid.pdf128.85 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan