Optimal Euler Circuit of Maximum Contiguous Cost(Graphs and Networks)
スポンサーリンク
概要
- 論文の詳細を見る
This paper introduces a new graph problem to find an Optimal Euler Circuit (OEC) in an Euler graph. OEC is defined as the Euler circuit that maximizes the sum of contiguous costs along it, where the contiguous cost is assigned for each of the two contiguous edges incident to a vertex. We prove that the OEC problem is NP-complete. A polynomial time algorithm will be presented for the case of a graph without vertex of degree greater than 4, and for the general case, a 1/4-approximation polynomial time algorithm will be proposed.
- 社団法人電子情報通信学会の論文
- 2007-01-01
著者
-
Qiao Yu
Graduate School Of Information Systems University Of Electro-communications
-
YASUHARA Makoto
University of Electrocommunications
-
Yasuhara Makoto
University Of Electro-communications
関連論文
- An Active Recognition of Handwritten Isolated Arabic Characters
- Optimal Euler Circuit of Maximum Contiguous Cost(Graphs and Networks)