著者

遠山 宏明 足立 暁生

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.37, no.11, pp.1886-1896, 1996-11-15

参考文献数

8

---

混合グラフのもとでのチャイニーズ・ポストマン問題(CPP)はNP完全であることが示されている. すべての辺の長さが等しい混合グラフ 平面混合グラフ 最大次数を3に制限した混合グラフのもとでさえNP完全である. 一方 グラフを全有向 または全無向に制限したCPPは多項式時間アルゴリズムを持つ. 本論文では 各辺の通行回数をたかだか2回に制限したCPP (2-CPP)がNP完全であり ちょうど1回に制限したCPP(1-CPP)はPに属することを示した. また CPP に関連する2つの興味ある関数の計算量も示した: (i)2-CPPにおいて 配達路の数を計算する関数は#P完全である (ii)CPPにおいて コスト k 以下で配達するためには 同一辺を少なくとも何回通行しなければならないかを計算する関数は多項式時間階層のクラスΔ^P_2に属する.The Chinese Postman Problem (CPP) on the mixed graphs is shown to be NP-complete. It remains NP-complete even if restricted to those whose edges all have equal length, or to the one on the mixed planner graphs, or to the one on the mixed graphs with nodes of degree three. CPP can be solved in polynomial time if the graph is either directed or undirected. In this paper, we show that even if the number of traverses for each edge is restricted to at most twice, CPP on the mixed graphs (called 2-CPP) is NP-complete, and if the number of traverses for each edge is restricted to exactly once, CPP on the mixed graphs (called 1-CPP)is in P. We also show complexity of two related functions: (i) in 2-CPP the function that calculates the number of delivery paths is #P-complete, oh the other band, (ii) in CPP the function that calculates the minimum of the maximum traverse numbers for each delivery path of cost k or less belongs to the class AZ in the polynomial time hierarchy.