Exact algorithms for graph homomorphisms

DOI10.1007/s00224-007-2007-xzbMath1119.68133OpenAlexW1979147290WikidataQ60488756 ScholiaQ60488756MaRDI QIDQ2642907

Dieter Kratsch, Pinar Heggernes, Fedor V. Fomin

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

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

Related Items

Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Exact algorithms for \(L(2,1)\)-labeling of graphs ⋮ Unnamed Item ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ Enumerating Minimal Tropical Connected Sets ⋮ New plain-exponential time classes for graph homomorphism ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs