[HTML][HTML] Chinese Postman Problem on edge-colored multigraphs
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 …
polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in …
Genetic algorithm for Chinese postman problems
J Hua, K Li-shan - Wuhan University Journal of Natural Sciences, 2003 - Springer
Abstract Chinese Postman Problem is an unsettled graphic problem. It was approached
seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese …
seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese …
The Chinese postman problem for mixed graphs
P Brucker - International Workshop on Graph-Theoretic Concepts …, 1980 - Springer
The chinese postman problem for mixed graphs Page 1 THE CHINESE POSTMAN PROBLEM
FOR MIXED GRAPHS BY PETER BRUCKER * Abstract: After introducing the concept of …
FOR MIXED GRAPHS BY PETER BRUCKER * Abstract: After introducing the concept of …
An optimal algorithm for the mixed Chinese postman problem
Y Nobert, JC Picard - Networks: An International Journal, 1996 - Wiley Online Library
Abstract The Chinese Postman Problem is well solved when the original graph contains only
arcs or only edges. The mixed Chinese Postman Problem (MCPP) is, however, NP …
arcs or only edges. The mixed Chinese Postman Problem (MCPP) is, however, NP …
A 3/2-approximation algorithm for the mixed postman problem
B Raghavachari, J Veerasamy - SIAM Journal on Discrete Mathematics, 1999 - SIAM
The mixed postman problem, a generalization of the Chinese postman problem, is that of
finding the shortest tour that traverses each edge of a given mixed graph (a graph containing …
finding the shortest tour that traverses each edge of a given mixed graph (a graph containing …
Postman problems on mixed graphs
FJ Zaragoza Martinez - 2003 - uwspace.uwaterloo.ca
The mixed postman problem consists of finding a minimum cost tour of a mixed graph M=(V,
E, A) traversing all its edges and arcs at least once. We prove that two well-known linear …
E, A) traversing all its edges and arcs at least once. We prove that two well-known linear …
The mixed Chinese postman problem parameterized by pathwidth and treedepth
In the mixed Chinese postman problem (MCPP), given a weighted mixed graph G (it may
have both edges and arcs), our aim is to find a closed walk of minimum weight traversing …
have both edges and arcs), our aim is to find a closed walk of minimum weight traversing …
Postman tour on a graph with precedence relation on arcs
Since the introduction of the Chinese Postman Problem (CPP), many variations on the same
theme have been developed. In this paper we examine still another variation. The arcs of the …
theme have been developed. In this paper we examine still another variation. The arcs of the …
Parameterized Directed-Chinese Postman Problem and Arc-Disjoint Cycles Problem on Euler Digraphs
Abstract In the Directed k-Chinese Postman Problem (k-DCPP), we are given a connected
weighted digraph G and asked to find k non-empty closed directed walks covering all arcs of …
weighted digraph G and asked to find k non-empty closed directed walks covering all arcs of …
Approximation algorithms for the mixed postman problem
B Raghavachari, J Veerasamy - … Conference Houston, Texas, June 22–24 …, 1998 - Springer
The mixed postman problem, a generalization of the Chinese postman problem, is that of
finding a shortest tour that traverses each edge of a given mixed graph (a graph containing …
finding a shortest tour that traverses each edge of a given mixed graph (a graph containing …