New plain-exponential time classes for graph homomorphism
DOI10.1007/s00224-010-9261-zzbMath1232.05138OpenAlexW2070374625MaRDI QIDQ639844
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
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)
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
