Please use this identifier to cite or link to this item:
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
Issue 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.
ISSN: 0963-5483
Appears in Collections:Computer Science
Mathematical Sciences

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.