New Plain-Exponential Time Classes for Graph Homomorphism

DOI10.1007/978-3-642-03351-3_32zbMATH Open1248.68264OpenAlexW1757413704MaRDI QIDQ3392969FDOQ3392969

Authors: Magnus Wahlström 

Publication date: 18 August 2009

Published in: Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_32

Recommendations

• New plain-exponential time classes for graph homomorphism
• Exact algorithms for graph homomorphisms
• Fundamentals of Computation Theory
• Lower bounds for the graph homomorphism problem
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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
• Title not available (Why is that?)
• 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

Cited In (7)

• The fine-grained complexity of graph homomorphism parameterized by clique-width
• Fundamentals of Computation Theory
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• Lower bounds for the graph homomorphism problem
• The homomorphism domination exponent
• New plain-exponential time classes for graph homomorphism
• 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 Q3392969)