New plain-exponential time classes for graph homomorphism
type: Item
instance of: scholarly article
title: New plain-exponential time classes for graph homomorphism
zbMATH Open document ID: 1232.05138
author: Magnus Wahlström
published in: Theory of Computing Systems
publication date: 2011-10-11T00:00:00Z
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5956664
zbMATH Keywords: graph homomorphism
zbMATH Keywords: exact algorithms
zbMATH Keywords: cliquewidth
MaRDI profile type: Publication
full work available at URL: s00224-010-9261-z
OpenAlex ID: W2070374625
cites work: Counting Subgraphs via Homomorphisms
cites work: Set Partitioning via Inclusion-Exclusion
cites work: New algorithms for exact satisfiability
cites work: Q4508369
cites work: Handle-rewriting hypergraph grammars
cites work: Upper bounds to the clique width of graphs
cites work: Small Maximal Independent Sets and Faster Exact Graph Coloring
cites work: Clique-width minimization is NP-hard
cites work: Exact algorithms for graph homomorphisms
cites work: Q4944973
cites work: The complexity of homomorphism and constraint satisfaction problems seen from the other side
cites work: A dichotomy for minimum cost graph homomorphisms
cites work: Minimum cost and list homomorphisms to semicomplete digraphs
cites work: Level of repair analysis and minimum cost homomorphisms of graphs
cites work: On the complexity of H-coloring
cites work: Which problems have strongly exponential complexity?
cites work: The Maximum Solution Problem on Graphs
cites work: A note on the complexity of the chromatic number problem
cites work: Approximating rank-width and clique-width quickly
cites work: The Time Complexity of Constraint Satisfaction
cites work: A new algorithm for optimal 2-constraint satisfaction and its implications
DOI: 10.1007/S00224-010-9261-Z
Recommended article: New Plain-Exponential Time Classes for Graph Homomorphism
Recommended article: Fundamentals of Computation Theory
Recommended article: Exact algorithms for graph homomorphisms
Recommended article: Q4952624
Recommended article: Q3490042
Recommended article: Approximation Algorithms for Graph Homomorphism Problems
Recommended article: Graph isomorphism in quasipolynomial time [extended abstract]
Recommended article: Q4535799
Recommended article: Parameterized complexity: exponential speed-up for planar graph problems
Recommended article: The Exponential Time complexity of counting (quantum) graph homomorphisms
description: scientific article; zbMATH DE number 5956664