Exact algorithms for graph homomorphisms

DOI10.1007/S00224-007-2007-XMaRDI QIDQ2642907zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch

Publication date 6 September 2007

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-007-2007-x

Mathematics Subject Classification ID

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) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Fundamentals of Computation Theory
• New Plain-Exponential Time Classes for Graph Homomorphism
• New plain-exponential time classes for graph homomorphism
• Lower bounds for the graph homomorphism problem
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs

Cited in

(19)

• On retracts, absolute retracts, and foldings in cographs
• Tight lower bounds for the complexity of multicoloring
• The fine-grained complexity of graph homomorphism parameterized by clique-width
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Fundamentals of Computation Theory
• An algorithm for the number of path homomorphisms
• Enumeration and maximum number of minimal connected vertex covers in graphs
• New Plain-Exponential Time Classes for Graph Homomorphism
• Counting homomorphisms in plain exponential time
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• scientific article; zbMATH DE number 1996252 (Why is no real title available?)
• Lower bounds for the graph homomorphism problem
• Enumerating Minimal Tropical Connected Sets
• Enumeration of minimal connected dominating sets for chordal graphs
• scientific article; zbMATH DE number 7651213 (Why is no real title available?)
• New plain-exponential time classes for graph homomorphism
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Homomorphisms of hexagonal graphs to odd cycles
• Exact algorithm for graph homomorphism and locally injective graph homomorphism

This page was built for publication: Exact algorithms for graph homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2642907)