An O(n) Time Algorithm to Find Cubic Subgraph in a Halin Graph

Ding Jun Lou; Jun Fu Liu

doi:10.4028/www.scientific.net/AMM.380-384.1318

Paper Titles

Research on the Construction Window Forecast of Immersed Tunnel Based on the Decision-Making Analysis
p.1302

Distinguishing Computer Graphics from Natural Images Based on Statistical Characteristics
p.1306

An Adaptive Prediction Algorithm Based on Maximum Correntropy Criterion
p.1310

Multi-Response Linear Polynomial Regression Models Designs
p.1314

An O(n) Time Algorithm to Find Cubic Subgraph in a Halin Graph
p.1318

Nonlinear Non-Gaussian Filtering Algorithm Based on Cubature Kalman and Particle Filter
p.1323

Network Layer Network Topology Discovery Algorithm Research
p.1327

The Role of Modelling in Agile Methodologies
p.1333

Using GPU and OpenACC to Accelerate the Maze Optimal Routing Algorithm
p.1338

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 380-384An O(n) Time Algorithm to Find Cubic Subgraph in a...

An O(n) Time Algorithm to Find Cubic Subgraph in a Halin Graph

Abstract:

The 3-Regular Subgraph Problem is: Given a graph G = (V, E), can we find a subgraph H = (V, E) in G such that for each vertex u in V, , where is the degree of u in H This problem is an NP-complete problem for general graphs. In this paper, we design an O(n) time algorithm to solve The 3-Regular Subgraph Problem for a Halin graph H, where n is the number of vertices of H. Given a Halin graph H, if there is a cubic subgraph G in H, then our algorithm will find G and give an answer Yes, otherwise our algorithm will give an answer No. We also prove the correctness of this algorithm.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 380-384)

Pages:

1318-1322

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.380-384.1318

Citation:

Cite this paper

Online since:

August 2013

Authors:

Ding Jun Lou, Jun Fu Liu

Keywords:

3-Regular Subgraph Problem, Correctness, Halin Graphs, O(n) Time Algorithm

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan Press, London, (1976).

Google Scholar

[2] J. A. Bondy, Pancyclic graphs: Recent Results, Infinite and Finite Sets [J]. Coll. Math. Soc. János Bolyai, 1975 10 181-187.

Google Scholar

[3] J. A. Bondy and L. Lovász, Lengths of cycles in Halin graphs [J]. Journal of Graph Theory, 1985 8 397-410.

DOI: 10.1002/jgt.3190090311

Google Scholar

[4] G. Cornuejols, D. Naddef and W. Pulleyblank, Halin graphs and the traveling salesman problem [J]. Math. Programming 1983 16 287-294.

DOI: 10.1007/bf02591867

Google Scholar

[5] M. R. Garey and D. S. Johnson, Computers and Intractability—A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, (1979).

Google Scholar

[6] R. Halin, Studies on minimally n-connected graphs, Combinatorial Mathematics and its Applications, Academic Press, London, 1971 129-136.

Google Scholar

[7] Yueping Li, Dingjun Lou, and Yunting Lu, Algorithms for the optimal Hamiltonian path in Halin graphs [J]. Ars Combinatoria 2008 87 235-255.

Google Scholar

[8] Dingjun Lou, Hamiltonian paths in Halin graphs [J]. Mathematica Applicata (Chinese) 1995 8 158-160.

Google Scholar

[9] Dingjun Lou and Huiquan Zhu, A note on max-leaves spanning tree problem in Halin graphs [J]. Australasian Journal of Combinatorics, 2004 29 95-97.

Google Scholar

[10] Dingjun Lou and Hongke Dou, A linear time algorithm for optimal bottleneck traveling salesman problem on a Halin graph, Proc. 2011 International Conference on Computer, Communication and Information Technology [C]. 2011 60-62.

Google Scholar

[11] J. M. Phillips, P. Punnen and S. N. Kabadi, A linear time algorithm for the bottleneck traveling salesman problem on a Halin graph [J]. Information Processing Letter 1998 67 105-110.

DOI: 10.1016/s0020-0190(98)00094-5

Google Scholar