New Plain-Exponential Time Classes for Graph Homomorphism

DOI10.1007/978-3-642-03351-3_32MaRDI QIDQ3392969zbMATH OpenOpenAlexFDO

Authors Magnus Wahlström

Publication date 18 August 2009

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03351-3_32

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• New plain-exponential time classes for graph homomorphism
• Exact algorithms for graph homomorphisms
• Fundamentals of Computation Theory
• Lower bounds for the graph homomorphism problem
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs

Cites work

• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• A dichotomy for minimum cost graph homomorphisms
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A note on the complexity of the chromatic number problem
• Clique-width minimization is NP-hard
• Exact algorithms for graph homomorphisms
• Handle-rewriting hypergraph grammars
• Level of repair analysis and minimum cost homomorphisms of graphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• New algorithms for exact satisfiability
• On the complexity of H-coloring
• Set partitioning via inclusion-exclusion
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• The Maximum Solution Problem on Graphs
• The Time Complexity of Constraint Satisfaction
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Upper bounds to the clique width of graphs
• Which problems have strongly exponential complexity?

Cited in

(7)

• The fine-grained complexity of graph homomorphism parameterized by clique-width
• Fundamentals of Computation Theory
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• Lower bounds for the graph homomorphism problem
• The homomorphism domination exponent
• New plain-exponential time classes for graph homomorphism
• Exact algorithms for graph homomorphisms

This page was built for publication: New Plain-Exponential Time Classes for Graph Homomorphism

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