%0 Conference Proceedings
%T Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width
%+ Vienna University of Technology = Technische Universität Wien (TU Wien)
%+ Technion - Israel Institute of Technology [Haifa]
%A Kotek, Tomer
%A Makowsky, Johann, A.
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 1st International Conference on Theoretical Computer Science (TTCS)
%C Tehran, Iran
%Y Mohammed Taghi Hajiaghayi
%Y Mohammad Reza Mousavi
%3 Topics in Theoretical Computer Science
%V LNCS-9541
%P 135-146
%8 2015-08-26
%D 2015
%R 10.1007/978-3-319-28678-5_10
%Z Computer Science [cs]Conference papers
%X Graph polynomials which are definable in Monadic Second Order Logic ($\mathrm {MSOL}$) on the vocabulary of graphs are Fixed-Parameter Tractable ($\mathrm {FPT}$) with respect to clique-width. In contrast, graph polynomials which are definable in $\mathrm {MSOL}$ on the vocabulary of hypergraphs are fixed-parameter tractable with respect to tree-width, but not necessarily with respect to clique-width. No algorithmic meta-theorem is known for the computation of graph polynomials definable in $\mathrm {MSOL}$ on the vocabulary of hypergraphs with respect to clique-width. We define an infinite class of such graph polynomials extending the class of graph polynomials definable in $\mathrm {MSOL}$ on the vocabulary of graphs and prove that they are Fixed-Parameter Polynomial Time ($\mathrm {FPPT}$ or $\mathrm {XP}$) computable, i.e. that they can be computed in time $O(n^{f(k)})$, where <i>n</i> is the number of vertices and <i>k</i> is the clique-width.
%G English
%Z TC 1
%Z WG 1.8
%2 https://inria.hal.science/hal-01446257/document
%2 https://inria.hal.science/hal-01446257/file/385217_1_En_10_Chapter.pdf
%L hal-01446257
%U https://inria.hal.science/hal-01446257
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9541
%~ IFIP-WG1-8
%~ IFIP-TTCS