Здравствуйте, True2008, Вы писали:

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

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

T>"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. "
Здесь написано, что задача для mixed graph является NP-hard.

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


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

T>"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...
T>"
T>de Bruijn graph — ориентированный(направленный), по нему Chinese postman problem (Shortest Chinese Superwalk) это NP-hard.
А это вообще к делу не относится. Скорее всего здесь речь про какую-то вариацию shortest common superstring.

В общем, у Вас какая-то путаница со сложностными классами, сведениями задач итд.