The week's pick
Reseach Article
Sufficient Conditions for Hamiltonicity in Communication Networks through Graph Modeling: New Research Challenges
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 164 - Number 2 |
| Year of Publication: 2017 |
| Authors: Ajeet Singh, Vikas Tiwari |
10.5120/ijca2017913578
|
Ajeet Singh, Vikas Tiwari . Sufficient Conditions for Hamiltonicity in Communication Networks through Graph Modeling: New Research Challenges. International Journal of Computer Applications. 164, 2 ( Apr 2017), 1-4. DOI=10.5120/ijca2017913578
Abstract
Graphs can be used to model various problems and relations in diverse domains eg. Computer Science, Biological, Chemical and many other. There exist various hard problems in communication networks, which are practically hard but can be shaped in the form of graphs. A Hamiltonian Path is a spanning trail in a network graph i.e. a path through every network node and a spanning cycle in a network graph is a Hamiltonian cycle. A network graph containing a Hamiltonian Cycle in it, is said to be Hamiltonian. The problem of finding whether a graph G is Hamiltonian is proved to be NPComplete. It cann’t be solved in a polynomial time. In this paper, state-of-the-art for existing degree related conditions for graphs to posses Hamiltonian cycle is presented. Later, various practical applications of Graph Theory in computer science are summarized. Future research directions in this perspective are also given at the end of this paper.
References
- Rao Li, ”A new sufficient condition for Hamiltonicity of graphs”, Elsevier, Information Processing Letters 98 (2006) 159161.
- Ferozuddin Riaz and Ferozuddin Riaz, ”Applications of Graph Theory in Computer Science”, 2011 IEEE Third International Conference on Computational Intelligence, Communication Systems and Networks.
- Ali Eshragh, ”Can Hamiltonian Cycle Problem be Solved with High Probability in Polynomial Time?”, School of Mathematical Sciences, The University of Adelaide, Adelaide SA 5005 Australia, February, 2012.
- Gerald L. Thompson, Sharad Singhal, ”A Successful Algorithm For The Undirected Hamiltonian Path Problem”, Carnegie-Mellon University Pittsburgh, 1984.
- Jordan Baumgardner, Karen Acker et. al., ”Solving a Hamiltonian Path Problem with a bacterial computer”, Journal of Biological Engineering, 2009.
- J.A. Bondy, U.S.R. Murty, ”Graph Theory with Applications”, Macmillan/Elsevier, London/New York, 1976.
- O. Ore, Note on Hamiltonian Circuits.
- N. Deo, ”Graph Theory:With applications to engineering and Computer Science”, PHI, Eastern Economy Edition.
- D.B. West, ”Introduction to Graph Theory”, Prentice-Hall, Inc., New Jersey.
- M.R. Garey and D.S. Jhonson, ”Computers and Intractability: A Guide to the Theory of NP Completeness”, W.H. Freeman and Company.
- K. Rosen, Discrete Mathematics and its Application, 6th Ed., McGraw-Hill.
- Ruud H. Teunter, Edo S. van der Poort, ”The maximum number of Hamiltonian cycles in graphs with a xed number of vertices and edges”, Operations Research Letters 26 (2000) 91-98.
- Israel A. Wagner, Alfred M. Bruckstein, ”Hamiltonian(t) - An Ant-Inspired Heuristic for Recognizing Hamiltonian Graphs”, (1999) IEEE.
- Guohun Zhu, Chunwei Song, Kaoru Hirota, F angyan Dong, Y onghua Wu, ”Necessary and Sufficient Conditions for Hamiltonian based on Linear Diophantine Equation Systems with Cycle Vector”, 2009 Third International Conference on Genetic and Evolutionary Computing.
- Lizhi Du, ”A Polynomial Time Algorithm for Hamilton Cycle (Path)”, intern. multi-conference of engineers and computer scientists, Mar 17-19, (2010), HongKong.
- Iain A. Stewart, ”Sufficient conditions for Hamiltonicity in multiswapped networks”, J. Parallel Distrib. Comput. 101 (2017) 1726.
- V.E. Alekseev, R. Boliac, D.V. Korobitsyn, V.V. Lozin, ”NPhard graph problems and boundary classes of graphs”, Theoretical Computer Science 389 (2007) 219-236, ELSEVIER.
Index Terms
Keywords