IEICE TRANSACTIONS on Fundamentals
A Note on Dual Trail Partition of a Plane Graph
Summary :
Given a plane graph G, a trail of G is said to be dual if it is also a trail in the geometric dual of G. We show that the problem of partitioning the edges of G into the minimum number of dual trails is NP-hard.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E74-A No.7 pp.1915-1917
- Publication Date
- 1991/07/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Graphs, Networks and Matroids
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
Shuichi UENO, Katsufumi TSUJI, Yoji KAJITANI, "A Note on Dual Trail Partition of a Plane Graph" in IEICE TRANSACTIONS on Fundamentals,
vol. E74-A, no. 7, pp. 1915-1917, July 1991, doi: .
Abstract: Given a plane graph G, a trail of G is said to be dual if it is also a trail in the geometric dual of G. We show that the problem of partitioning the edges of G into the minimum number of dual trails is NP-hard.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e74-a_7_1915/_p
Copy
@ARTICLE{e74-a_7_1915,
author={Shuichi UENO, Katsufumi TSUJI, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on Dual Trail Partition of a Plane Graph},
year={1991},
volume={E74-A},
number={7},
pages={1915-1917},
abstract={Given a plane graph G, a trail of G is said to be dual if it is also a trail in the geometric dual of G. We show that the problem of partitioning the edges of G into the minimum number of dual trails is NP-hard.},
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - A Note on Dual Trail Partition of a Plane Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1915
EP - 1917
AU - Shuichi UENO
AU - Katsufumi TSUJI
AU - Yoji KAJITANI
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E74-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 1991
AB - Given a plane graph G, a trail of G is said to be dual if it is also a trail in the geometric dual of G. We show that the problem of partitioning the edges of G into the minimum number of dual trails is NP-hard.
ER -
English
