Optimal Euler Circuit of Maximum Contiguous Cost
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.1 pp.274-280
- Publication Date
- 2007/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e90-a.1.274
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yu QIAO, Makoto YASUHARA, "Optimal Euler Circuit of Maximum Contiguous Cost" in IEICE TRANSACTIONS on Fundamentals,
vol. E90-A, no. 1, pp. 274-280, January 2007, doi: 10.1093/ietfec/e90-a.1.274.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.1.274/_p
Copy
@ARTICLE{e90-a_1_274,
author={Yu QIAO, Makoto YASUHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Optimal Euler Circuit of Maximum Contiguous Cost},
year={2007},
volume={E90-A},
number={1},
pages={274-280},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e90-a.1.274},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Optimal Euler Circuit of Maximum Contiguous Cost
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 274
EP - 280
AU - Yu QIAO
AU - Makoto YASUHARA
PY - 2007
DO - 10.1093/ietfec/e90-a.1.274
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2007
AB - 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.
ER -
English
