New plain-exponential time classes for graph homomorphism
DOI10.1007/S00224-010-9261-ZzbMATH Open1232.05138OpenAlexW2070374625MaRDI QIDQ639844FDOQ639844
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
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
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)
Cites Work
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- On the complexity of H-coloring
- Which problems have strongly exponential complexity?
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Exact algorithms for graph homomorphisms
- The Time Complexity of Constraint Satisfaction
- Set partitioning via inclusion-exclusion
- A note on the complexity of the chromatic number problem
- The Maximum Solution Problem on Graphs
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- Counting Subgraphs via Homomorphisms
- Title not available (Why is that?)
- Approximating rank-width and clique-width quickly
- A dichotomy for minimum cost graph homomorphisms
- Minimum cost and list homomorphisms to semicomplete digraphs
- New algorithms for exact satisfiability
- Level of repair analysis and minimum cost homomorphisms of graphs
- Clique-width minimization is NP-hard
- Title not available (Why is that?)
Cited In (10)
- Tight lower bounds for the complexity of multicoloring
- The fine-grained complexity of graph homomorphism parameterized by clique-width
- Fundamentals of Computation Theory
- New Plain-Exponential Time Classes for Graph Homomorphism
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Title not available (Why is that?)
- Lower bounds for the graph homomorphism problem
- The homomorphism domination exponent
- Title not available (Why is that?)
- Exact algorithms for graph homomorphisms
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)
