Computing Graph Polynomials on Graphs of Bounded Clique-Width

DOI10.1007/11917496_18MaRDI QIDQ3522957zbMATH OpenOpenAlexWikidataFDO

Authors Ilya Averbouch, B. Godlin, Johann A. Makowsky, Udi Rotics

Publication date 4 September 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11917496_18

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width
• Graph-Theoretic Concepts in Computer Science
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• scientific article; zbMATH DE number 6850484
• Better polynomial algorithms on graphs of bounded rank-width
• scientific article; zbMATH DE number 2044928
• Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)
• Graphs of bounded cliquewidth are polynomially -bounded
• Complexity of graph polynomials

Cited in

(24)

• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width
• Computing the clique number of \(a\)-perfect graphs in polynomial time
• Computing the clique-width of cactus graphs
• Harary polynomials
• An extension of the bivariate chromatic polynomial
• Efficient computation of generalized Ising polynomials on graphs with fixed clique-width
• Eigenvalue location in graphs of small clique-width
• Counting problems in parameterized complexity
• Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs
• A little statistical mechanics for the graph theorist
• A Most General Edge Elimination Polynomial
• Locating the eigenvalues for graphs of small clique-width
• Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width
• My writing
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• The enumeration of vertex induced subgraphs with respect to the number of components
• Inductive computations on graphs defined by clique-width expressions
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Multi-clique-width
• Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
• Hierarchical and modularly-minimal vertex colorings
• scientific article; zbMATH DE number 6850484 (Why is no real title available?)

This page was built for publication: Computing Graph Polynomials on Graphs of Bounded Clique-Width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3522957)