New plain-exponential time classes for graph homomorphism

DOI10.1007/S00224-010-9261-ZMaRDI QIDQ639844zbMATH OpenOpenAlexFDO

Authors Magnus Wahlström

Publication date 11 October 2011

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-010-9261-z

zbMATH Keywords

exact algorithmsgraph homomorphismcliquewidth

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• New Plain-Exponential Time Classes for Graph Homomorphism
• Fundamentals of Computation Theory
• Exact algorithms for graph homomorphisms
• Publication:4952624
• scientific article; zbMATH DE number 4162940
• Approximation Algorithms for Graph Homomorphism Problems
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 1756013
• Parameterized complexity: exponential speed-up for planar graph problems
• The Exponential Time complexity of counting (quantum) graph homomorphisms

Cites work

• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 1420904 (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
• Approximating rank-width and clique-width quickly
• Clique-width minimization is NP-hard
• Counting Subgraphs via Homomorphisms
• 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

(10)

• Lower bounds for the graph homomorphism problem
• scientific article; zbMATH DE number 7651213 (Why is no real title available?)
• The homomorphism domination exponent
• New Plain-Exponential Time Classes for Graph Homomorphism
• Fundamentals of Computation Theory
• Tight lower bounds for the complexity of multicoloring
• scientific article; zbMATH DE number 2151253 (Why is no real title available?)
• Exact algorithms for graph homomorphisms
• The fine-grained complexity of graph homomorphism parameterized by clique-width
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs

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 Q639844)