New Plain-Exponential Time Classes for Graph Homomorphism

DOI10.1007/978-3-642-03351-3_32zbMath1248.68264OpenAlexW1757413704MaRDI QIDQ3392969

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

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

• 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

This page was built for publication: New Plain-Exponential Time Classes for Graph Homomorphism