The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree

1. Averbouch, I., Godlin, B., Makowsky, J.A.: A most general edge elimination polynomial. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 31–42. Springer, Heidelberg (2008)

   Chapter  Google Scholar 

2. Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Computing the Tutte polynomial in vertex-exponential time. In: FOCS 2008, pp. 677–686 (2008)

   Google Scholar 

3. Bläser, M., Dell, H.: Complexity of the cover polynomial. In: ICALP, pp. 801–812 (2007)

   Google Scholar 

4. Bläser, M., Dell, H., Fouz, M.: Complexity and approximability of the cover polynomial. Computation Complexity (accepted)

   Google Scholar 

5. Bläser, M., Dell, H., Makowsky, J.A.: Complexity of the bollobás-riordan polynomial. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science – Theory and Applications. LNCS, vol. 5010, pp. 86–98. Springer, Heidelberg (2008)

   Chapter  Google Scholar 

6. Bläser, M., Hoffmann, C.: On the complexity of the interlace polynomial. In: Albers, S., Weil, P. (eds.) 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Dagstuhl, Germany, pp. 97–108 (2008)

   Google Scholar 

7. Bollobás, B., Riordan, O.: A Tutte polynomial for coloured graphs. Combinatorics, Probability and Computing 8(1-2), 45–93 (1999)

   Article  MathSciNet  MATH  Google Scholar 

8. Cai, J.-y., Lu, P., Xia, M.: Holographic algorithms with matchgates capture precisely tractable planar #CSP. CoRR abs/1008.0683 (2010)

   Google Scholar 

9. Chung, F.R.K., Graham, R.L.: On the cover polynomial of a digraph. J. Combin. Theory Ser. B 65, 273–290 (1995)

   Article  MathSciNet  MATH  Google Scholar 

10. Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics 108(1-2), 23–52 (2001)

    Article  MathSciNet  MATH  Google Scholar 

11. D’Antona, O.M., Munarini, E.: The cycle-path indicator polynomial of a digraph. Advances in Applied Mathematics 25(1), 41–56 (2000)

    Article  MathSciNet  MATH  Google Scholar 

12. Goldberg, L.A., Jerrum, M.: Inapproximability of the Tutte polynomial. Inform. Comput. 206(7), 908–929 (2008)

    Article  MathSciNet  MATH  Google Scholar 

13. Goldberg, L.A., Jerrum, M.: Inapproximability of the Tutte polynomial of a planar graph. CoRR abs/0907.1724 (2009)

    Google Scholar 

14. Hoffmann, C.: A most general edge elimination polynomial - thickening of edges. Fundam. Inform. 98(4), 373–378 (2010)

    MATH  Google Scholar 

15. Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. of the Cambridge Phil. Society 108(1), 35–53 (1990)

    Article  MathSciNet  MATH  Google Scholar 

16. Linial, N.: Hard enumeration problems in geometry and combinatorics. SIAM J. Algebraic Discrete Methods 7(2), 331–335 (1986)

    Article  MathSciNet  MATH  Google Scholar 

17. Lotz, M., Makowsky, J.A.: On the algebraic complexity of some families of coloured Tutte polynomials. Advances in Applied Mathematics 32(1), 327–349 (2004)

    Article  MathSciNet  MATH  Google Scholar 

18. Makowsky, J.A.: From a zoo to a zoology: Towards a general theory of graph polynomials. Theory of Computing Systems 43(3), 542–562 (2008)

    Article  MathSciNet  MATH  Google Scholar 

19. Valiant, L.G.: Holographic algorithms (extended abstract). In: FOCS 2004: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 306–315. IEEE Computer Society, Washington, DC (2004)

    Chapter  Google Scholar 

20. Vertigan, D.L.: The computational complexity of Tutte invariants for planar graphs. SIAM J. Comput. 35(3), 690–712 (2005)

    Article  MathSciNet  Google Scholar 

21. Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theoretical Computer Science 384(1), 111–125 (2007)

    Article  MathSciNet  MATH  Google Scholar 

Download references