𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimum Cost Homomorphism Dichotomy for Oriented Cycles

✍ Scribed by Gregory Gutin; Arash Rafiey; Anders Yeo

Publisher
Springer Japan
Year
2009
Tongue
English
Weight
179 KB
Volume
25
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A Polynomial Algorithm for Homomorphisms
A Polynomial Algorithm for Homomorphisms to Oriented Cycles
✍ X.D. Zhu πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 559 KB

W. Gutjahr, E. Welzl, and G. Woeginger have given a polynomial time algorithm to decide whether a given digraph is homomorphic to an oriented path. The corresponding problem for oriented cycles (i.e., given a digraph \(G\), is it homomorphic to a fixed oriented cycle \(C\) ?) remained open. We prove