New plain-exponential time classes for graph homomorphism

DOI10.1007/s00224-010-9261-zzbMath1232.05138OpenAlexW2070374625MaRDI QIDQ639844

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

graph homomorphismexact algorithmscliquewidth

Mathematics Subject Classification ID

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

Related Items (5)

Lower Bounds for the Graph Homomorphism Problem ⋮ A SAT Approach to Clique-Width ⋮ Unnamed Item ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• A note on the complexity of the chromatic number problem
• Which problems have strongly exponential complexity?
• New algorithms for exact satisfiability
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• A dichotomy for minimum cost graph homomorphisms
• Level of repair analysis and minimum cost homomorphisms of graphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Exact algorithms for graph homomorphisms
• Clique-width minimization is NP-hard
• The Time Complexity of Constraint Satisfaction
• The Maximum Solution Problem on Graphs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Set Partitioning via Inclusion-Exclusion
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• Approximating rank-width and clique-width quickly
• Counting Subgraphs via Homomorphisms

This page was built for publication: New plain-exponential time classes for graph homomorphism