Chinese postman problem на направленных графах имеет класс сложности NP-hard ?

Mab>Нет, эта задача сводится к потоку минимальной стоимости.

как это нет? заблуждение!
кстати, не знаете, где найти статью "Кибернетический сборник, новая серия, вып.6 М., Мир, 1969, С.33-40." ?

http://www.nist.gov/dads/HTML/chinesePostman.html

"Definition: Find a minimum length closed walk that traverses each edge at least once. Finding an optimal solution in a graph with both directed and undirected edges is NP-complete. "

направленный граф и ориентированный граф это одно и то же. ориентированный и неориентированный графы являются частными случаями смешанного. силлогизм: для смешанного графа — Chinese postman problem NP-hard, следовательно для ориентированного(направленного), частного случая смешанного, Chinese postman problem так же NP-hard.

http://www.youtube.com/watch?v=-m7PFnSvmJM

"In the first half of the talk I will discuss several algorithmic results affecting whole genome assembly -- the problem of assembling a genome from short pieces (called reads). This problem is often reduced to various path problems on graphs. We will first show that the problem of finding the Shortest Chinese Superwalk on a de Bruijn graph is NP-complete/hard, hence demonstrating the computational equivalence of two methods for sequenceassembly: the String Graph approach of Myers et al and the Eulerian Superpath approach of Pevzner et al. We will also demonstrate a simple polynomial time algorithm separating complimentary paths on a graph, which is...
"
de Bruijn graph — ориентированный(направленный), по нему Chinese postman problem (Shortest Chinese Superwalk) это NP-hard.