Name
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1017/S0963548305007285 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
particular size,generating function,two-variable rank generating function,graphic 2-polymatroid,particular number,rank generating function,computational complexity,graph,matroid | Matroid,Generating function,Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Polymatroid,Rank (graph theory),Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
15 | 3 | 0963-5483 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. D. Noble | 1 | 83 | 9.56 |