Paths and trails in edge-colored weighted graphs
Paths and trails in edge-colored weighted graphs
复制标题
边缘颜色加权图中的路径和踪迹
DOI：
10.1016/j.tcs.2019.09.048
复制
发表时间：
2019-12
影响因子：
1.1
通讯作者：
Huang Fei
中科院分区：
文献类型：
--
作者：
Miao Runjie;Yuan Jinjiang;Huang Fei
Abstract Let (G, c, w) be an edge-colored weighted graph, where G is a nontrivial connected graph, c is an edge-coloring of G, and w is an edge-weighting of G. A path, a trail, a cycle, or a closed trail of G, say F, is called proper under the edge-coloring c if every two consecutive edges of F receive different colors in c. Let s and t be two specified nonadjacent vertices in G. In this paper, we study the problems for finding, in (G, c, w), the minimum weighted proper s-t-path, the minimum weighted proper s-t-trail, the minimum weighted proper cycle, the minimum weighted proper closed trail, the maximum weighted proper s-t-path, and the maximum weighted proper s-t-trail. When the minimization problems are considered we assume that (G, c, w) has no negative proper cycle, and when the maximization problems are considered we assume that (G, c, w) has no proper closed trail. We show that all these problems are solvable in polynomial time.
登录
查看更多内容
DOI：
--
发表时间：
1989
期刊：
--
影响因子：
--
作者：
G. Nemhauser;A. Kan
通讯作者：
G. Nemhauser;A. Kan
DOI：
10.1016/j.endm.2009.11.037
发表时间：
2009-12
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
L. Gourvès;Adria Lyra;C. Martinhon;J. Monnot;Fábio Protti
通讯作者：
L. Gourvès;Adria Lyra;C. Martinhon;J. Monnot;Fábio Protti
影响因子：
0.9
作者：
A. Abouelaoualim;K. Das;W. F. D. L. Vega;Marek Karpinski;Y. Manoussakis;C. Martinhon;R. Saad
通讯作者：
A. Abouelaoualim;K. Das;W. F. D. L. Vega;Marek Karpinski;Y. Manoussakis;C. Martinhon;R. Saad
DOI：
10.1007/978-3-642-02029-2_19
发表时间：
2008-05
期刊：
ArXiv
影响因子：
--
作者：
G. Gutin;Eun Jung Kim
通讯作者：
G. Gutin;Eun Jung Kim
影响因子：
2.7
作者：
V. CherkasskyBoris;V. GoldbergAndrew;RadzikTomasz
通讯作者：
V. CherkasskyBoris;V. GoldbergAndrew;RadzikTomasz