[HTML][HTML] Chinese Postman Problem on edge-colored multigraphs
Discrete Applied Mathematics, 2017•Elsevier
It is well-known that the Chinese Postman Problem on undirected and directed graphs is
polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in
sharp contrast to the Chinese Postman Problem on mixed graphs, ie, graphs with directed
and undirected edges, for which the problem is NP-hard.
polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in
sharp contrast to the Chinese Postman Problem on mixed graphs, ie, graphs with directed
and undirected edges, for which the problem is NP-hard.
Abstract
It is well-known that the Chinese Postman Problem on undirected and directed graphs is polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in sharp contrast to the Chinese Postman Problem on mixed graphs, i.e., graphs with directed and undirected edges, for which the problem is NP-hard.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果