Loading...
Please wait, while we are loading the content...
A Graph Polynomial for Independent Sets of Bipartite Graphs
| Content Provider | Scilit |
|---|---|
| Author | Ge, Q. Štefankovič, D. |
| Copyright Year | 2012 |
| Description | We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings, the number of perfect matchings, and, for bipartite graphs, the number of independent sets (#BIS). We analyse the complexity of exact evaluation of the polynomial at rational points and show a dichotomy result: for most points exact evaluation is #P-hard (assuming the generalized Riemann hypothesis) and for the rest of the points exact evaluation is trivial. |
| Related Links | http://arxiv.org/pdf/0911.4732 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/6B5805215422978D0652DB126712596B/S0963548312000296a.pdf/div-class-title-a-graph-polynomial-for-independent-sets-of-bipartite-graphs-div.pdf |
| Ending Page | 714 |
| Page Count | 20 |
| Starting Page | 695 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548312000296 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 5 |
| Volume Number | 21 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2012-09-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Primary 05c31 Secondary 03d15 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
