New plain-exponential time classes for graph homomorphism
From MaRDI portal
Publication:639844
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
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
