A Polynomial Algorithm for Homomorphisms to Oriented Cycles

✍ Scribed by X.D. Zhu

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 559 KB
• Volume: 19
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1995.1040

✦ Synopsis

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 that if (C) is an unbalanced cycle then this problem is polynomial time decidable. 1995 Academic Press, Inc.