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

cliquewidthexact algorithmsgraph homomorphism

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• New Plain-Exponential Time Classes for Graph Homomorphism
• Fundamentals of Computation Theory
• Exact algorithms for graph homomorphisms
• scientific article; zbMATH DE number 1445311
• 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

• 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
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• 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 complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Maximum Solution Problem on Graphs
• The Time Complexity of Constraint Satisfaction
• Upper bounds to the clique width of graphs
• Which problems have strongly exponential complexity?

Cited in

(14)

• Exact algorithms for graph homomorphisms
• New Plain-Exponential Time Classes for Graph Homomorphism
• Lower bounds for the graph homomorphism problem
• scientific article; zbMATH DE number 2151253 (Why is no real title available?)
• The Complexity of Homomorphism Indistinguishability
• Tight lower bounds for the complexity of multicoloring
• Fundamentals of Computation Theory
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• scientific article; zbMATH DE number 7651213 (Why is no real title available?)
• The homomorphism domination exponent
• The fine-grained complexity of graph homomorphism parameterized by clique-width
• The fine-grained complexity of graph homomorphism parameterized by clique-width
• Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
• Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings

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)