A Linear Time Algorithm for the Line Subgraph Problem in Halin Graphs
- 10.2991/amsm-16.2016.37How to use a DOI?
- halin graph; line graph; linear time algorithm
Given a graph G= (V,E ) and a positive integer p" "|E|. The Line Subgraph Problem is: Is there a subset E'" "E such that |E'|" "p and H= (V,E ) is a line graph. In this paper, we design a linear time algorithm to solve the line subgraph problem for Halin graphs. The algorithm is optimal.
- © 2016, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Dingjun Lou AU - Jun Liang AU - Guanpu Han PY - 2016/05 DA - 2016/05 TI - A Linear Time Algorithm for the Line Subgraph Problem in Halin Graphs BT - Proceedings of the 2016 International Conference on Applied Mathematics, Simulation and Modelling PB - Atlantis Press SP - 161 EP - 164 SN - 2352-538X UR - https://doi.org/10.2991/amsm-16.2016.37 DO - 10.2991/amsm-16.2016.37 ID - Lou2016/05 ER -