کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419402 | 683798 | 2013 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Complexity of trails, paths and circuits in arc-colored digraphs Complexity of trails, paths and circuits in arc-colored digraphs](/preview/png/419402.png)
We deal with different algorithmic questions regarding properly arc-colored s–ts–t trails, paths and circuits in arc-colored digraphs. Given an arc-colored digraph DcDc with c≥2c≥2 colors, we show that the problem of determining the maximum number of arc disjoint properly arc-colored s–ts–t trails can be solved in polynomial time. Surprisingly, we prove that the determination of a properly arc-colored s–ts–t path is NP -complete even for planar digraphs containing no properly arc-colored circuits and c=Ω(n)c=Ω(n), where nn denotes the number of vertices in DcDc. If the digraph is an arc-colored tournament, we show that deciding whether it contains a properly arc-colored circuit passing through a given vertex xx (resp., properly arc-colored Hamiltonian s–ts–t path) is NP -complete for c≥2c≥2. As a consequence, we solve a weak version of an open problem posed in Gutin et al. (1998) [23], whose objective is to determine whether a 22-arc-colored tournament contains a properly arc-colored circuit.
Journal: Discrete Applied Mathematics - Volume 161, Issue 6, April 2013, Pages 819–828