Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants

DOI10.1007/978-3-540-69407-6_43zbMath1142.68459OpenAlexW1539362580MaRDI QIDQ3507454

Johann A. Makowsky

Publication date: 19 June 2008

Published in: Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69407-6_43

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A two-variable interlace polynomial
• The interlace polynomial of a graph
• From a zoo to a zoology: Towards a general theory of graph polynomials
• A weighted graph polynomial from chromatic invariants of knots
• On the algebraic complexity of some families of coloured Tutte polynomials
• On the cover polynomial of a digraph
• The complexity of partition functions
• On the Harmonious Coloring of Graphs
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Complexity of the Bollobás-Riordan Polynomial
• Edge coloring models and reflection positivity
• A Tutte Polynomial for Coloured Graphs
• On the computational complexity of the Jones and Tutte polynomials
• On the Complexity of the Interlace Polynomial
• Complexity of the Cover Polynomial