|
|
|
|
ON THE COMPLEXITY OF THE COLORFUL DIRECTED PATHS IN VERTEX COLORING OF DIGRAPHS
|
|
|
|
|
|
|
|
نویسنده
|
مولا احمدی اِ. ,سقاییان س. ,دهقان ا.
|
|
منبع
|
transactions on combinatorics - 2013 - دوره : 2 - شماره : 2 - صفحه:1 -7
|
|
چکیده
|
The colorful paths and rainbow paths have been considered by several authors. a colorfuldirected path in a digraph g is a directed path with (g) vertices whose colors are different. a v-colorful directed path is such a directed path, starting from v. we prove that for a given 3-regulartriangle-free digraph g determining whether there is a proper (g)-coloring of g such that for everyv 2 v (g), there exists a v-colorful directed path is np-complete.
|
|
کلیدواژه
|
Colorful Directed Paths ,Computational Complexity ,Vertex Coloring
|
|
آدرس
|
sharif university of technology, Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran, ایران, islamic azad university, Department of Computer, Abadan Branch, Islamic Azad University, Abadan, Iran, ایران, amirkabir university of technology, Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran, ایران
|
|
پست الکترونیکی
|
ali dehghan16@aut.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|