A Linear Time Algorithm for the Line Subgraph Problem in Halin Graphs

DOI

10.2991/amsm-16.2016.37How to use a DOI?

Keywords

halin graph; line graph; linear time algorithm

Abstract

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.

Copyright

© 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/).

Download article (PDF)

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  -