.
_:Nc57da59c0b8346f5afec5cc9ad5bfb1a _:Nb67b3e5a56914d9bba62351627d97849 .
"en" .
"1-13" .
_:N53cfd6639d1f4ac4b7f72703085f7275 "Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India" .
"2019-04-11T11:03" .
.
"Computation Theory and Mathematics" .
.
.
_:Nd4f9c013694244d3b890785cf1473123 "Divya" .
"https://link.springer.com/10.1007%2Fs12572-018-00243-0" .
_:N46bcb883825a42ba9e11fa187e40c711 "doi" .
"articles" .
_:Na5bad0a25bbb433a947a6f175489ab13 .
_:N06a89ec822854074b3331d513cc55e61 "Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India" .
_:Nb30fa816e79347c18b481d24b7acf1f0 _:Nc57da59c0b8346f5afec5cc9ad5bfb1a .
.
_:N8d171d4928784d52a6ed72ad3d65f5b4 "Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India" .
_:N58b6a95f74ec4be7aedf003e49d7c2c7 .
"0975-0770" .
.
.
.
"Information and Computing Sciences" .
_:N58b6a95f74ec4be7aedf003e49d7c2c7 "readcube_id" .
.
"false"^^ .
_:Nc57da59c0b8346f5afec5cc9ad5bfb1a _:Nd4f9c013694244d3b890785cf1473123 .
.
"International Journal of Advances in Engineering Sciences and Applied Mathematics" .
.
_:Nd4f9c013694244d3b890785cf1473123 _:N06a89ec822854074b3331d513cc55e61 .
_:Nd4f9c013694244d3b890785cf1473123 .
_:N8d171d4928784d52a6ed72ad3d65f5b4 .
_:Nd92b973ec3914d9f9adb89feed847ea1 "dimensions_id" .
_:Nb30fa816e79347c18b481d24b7acf1f0 _:Ne68a4751bb234a9886bdddb3668593d7 .
"2019-03-04" .
.
.
"https://scigraph.springernature.com/explorer/license/" .
"A convex bipartite graph G with bipartition (X, Y) and an ordering X=(x1,\u2026,xn) is a bipartite graph such that for each y\u2208Y, the neighborhood of y in X appears consecutively. G is said to have convexity with respect to X. In this paper, we present a necessary and sufficient condition for the existence of a Hamiltonian cycle in convex bipartite graphs, and further, we obtain a linear-time algorithm for this graph class. We also show that Chvatal\u2019s necessary condition is sufficient for convex bipartite graphs. The closely related problem is HAMILTONIAN PATH whose complexity is open in convex bipartite graphs. We classify the class of convex bipartite graphs as monotone and non-monotone graphs. For monotone convex bipartite graphs, we present a linear-time algorithm to output a Hamiltonian path. It is important to highlight that: (a) in Keil (Inf Process Lett 20:201\u2013206, 1985) and Ghosh (in: WALCOM 2011, LNCS 6552, pp. 191\u2013201, 2011), it is incorrectly claimed that Hamiltonian path problem in convex bipartite graphs is polynomial-time solvable by referring to Muller (Discrete Math 156:291\u2013298, 1996) which actually discusses Hamiltonian cycle and (b) the algorithm appeared in Ghosh (2011) for the longest path problem (Hamiltonian path problem) in biconvex and convex bipartite graphs has an error and it does not compute an optimum solution always. We present an infinite set of counterexamples in support of our claim." .
_:N53cfd6639d1f4ac4b7f72703085f7275 .
"research_article" .
_:Nb30fa816e79347c18b481d24b7acf1f0 .
_:N46bcb883825a42ba9e11fa187e40c711 "10.1007/s12572-018-00243-0" .
_:N46bcb883825a42ba9e11fa187e40c711 .
.
_:Ne68a4751bb234a9886bdddb3668593d7 _:N8d171d4928784d52a6ed72ad3d65f5b4 .
_:Nb67b3e5a56914d9bba62351627d97849 .
.
.
.
_:N46bcb883825a42ba9e11fa187e40c711 .
.
.
_:N58b6a95f74ec4be7aedf003e49d7c2c7 "88b4c17327970b989df188ce2ace0ab0574917b6300648956a4e3a2e019f2bcf" .
"0975-5616" .
.
_:Na5bad0a25bbb433a947a6f175489ab13 .
.
_:Na5bad0a25bbb433a947a6f175489ab13 "Springer Nature - SN SciGraph project" .
.
_:Nd4f9c013694244d3b890785cf1473123 "V." .
.
_:Nb67b3e5a56914d9bba62351627d97849 _:Nbbe86509610f4569a5f9c7eeec0bf42e .
.
_:Nd92b973ec3914d9f9adb89feed847ea1 "pub.1112520115" .
.
.
.
.
.
_:N06a89ec822854074b3331d513cc55e61 .
_:Ne68a4751bb234a9886bdddb3668593d7 "Kowsika" .
.
_:Nbbe86509610f4569a5f9c7eeec0bf42e _:N53cfd6639d1f4ac4b7f72703085f7275 .
.
.
_:Nd92b973ec3914d9f9adb89feed847ea1 .
_:Nbbe86509610f4569a5f9c7eeec0bf42e "N." .
.
"Hamiltonicity in convex bipartite graphs" .
"2019-03-04" .
.
_:Ne68a4751bb234a9886bdddb3668593d7 .
_:N58b6a95f74ec4be7aedf003e49d7c2c7 .
_:Nbbe86509610f4569a5f9c7eeec0bf42e .
_:Nbbe86509610f4569a5f9c7eeec0bf42e "Sadagopan" .
.
_:Nd92b973ec3914d9f9adb89feed847ea1 .
_:Ne68a4751bb234a9886bdddb3668593d7 "P." .