Proceedings of the 2016 International Conference on Applied Mathematics, Simulation and Modelling

<Previous Article In Volume
Next Article In Volume>

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

Authors
Dingjun Lou, Jun Liang, Guanpu Han
Corresponding Author
Dingjun Lou
Available Online May 2016.
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)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the 2016 International Conference on Applied Mathematics, Simulation and Modelling
Series
Advances in Computer Science Research
Publication Date
May 2016
ISBN
10.2991/amsm-16.2016.37
ISSN
2352-538X
DOI
10.2991/amsm-16.2016.37How to use a DOI?
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/).

Cite this article

risenwbib
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  -