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

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

(20)

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

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)