Paths through fixed vertices in edge-colored graphs
Paths through fixed vertices in edge-colored graphs
复制标题
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
W. Chow;Y. Manoussakis;O. Megalakaki;Michael Spyratos;Z. Tuza
中科院分区：
文献类型：
--
作者：
W. Chow;Y. Manoussakis;O. Megalakaki;Michael Spyratos;Z. Tuza
另一条链条、一条通行证。不同的颜色、不同的颜色。再加上严谨的理性认识，问题是NP-Complet dans le cas de graph es 2-aretes-colres。L问题的存在使得L的多项式在图解上变得更加完整。S，t)-Chaine(这是一条可怕的单色链条，S的单色单色链条是不同的)，这是一种快乐的颜色。
Chaines alternees passant par des sommets donnes dans des graphes aretes-colores. Nous etudions le probleme de trouver dans un graphe aretes-colore une chaine alternee joignant deux sommets donnes et passant par des sommets donnes (une chaine est alternee si deux aretes adjacentes arbitraires ont des couleurs differentes). Plus precisement nous demontrons que ce probleme est NP-complet dans le cas de graphes 2-aretes-colores. Ensuite nous montrons que le probleme de l'existence d'une telle chaine est polynomial dans le cas ou l'on se restreint aux graphes complets 2-aretes-colores. Nous etudions egalement le probleme de trouver une (s,t)-chaine (c'est-a-dire une chaine de longueur s+t qui se partage en deux sous-chaines monochromatiques de couleurs differentes) joignant deux sommets donnes et passant par des sommets donnes, dans un graphe complet aretes-colore.