Hamiltonicity in convex bipartite graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-04

AUTHORS

P. Kowsika, V. Divya, N. Sadagopan

ABSTRACT

A convex bipartite graph G with bipartition (X, Y) and an ordering X=(x1,…,xn) is a bipartite graph such that for each y∈Y, 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’s 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–206, 1985) and Ghosh (in: WALCOM 2011, LNCS 6552, pp. 191–201, 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–298, 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. More... »

PAGES

1-13

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s12572-018-00243-0

DOI

http://dx.doi.org/10.1007/s12572-018-00243-0

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1112520115


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kowsika", 
        "givenName": "P.", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Divya", 
        "givenName": "V.", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sadagopan", 
        "givenName": "N.", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0020-0190(85)90050-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011139166"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(85)90050-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011139166"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(95)00057-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019406771"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-19094-0_20", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019564675", 
          "https://doi.org/10.1007/978-3-642-19094-0_20"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-19094-0_20", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019564675", 
          "https://doi.org/10.1007/978-3-642-19094-0_20"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-03816-7_35", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034196859", 
          "https://doi.org/10.1007/978-3-642-03816-7_35"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2007.02.010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045057680"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054107005054", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062896798"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4153/cjm-1964-055-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072264594"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-03-04", 
    "datePublishedReg": "2019-03-04", 
    "description": "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.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s12572-018-00243-0", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1050051", 
        "issn": [
          "0975-0770", 
          "0975-5616"
        ], 
        "name": "International Journal of Advances in Engineering Sciences and Applied Mathematics", 
        "type": "Periodical"
      }
    ], 
    "name": "Hamiltonicity in convex bipartite graphs", 
    "pagination": "1-13", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "88b4c17327970b989df188ce2ace0ab0574917b6300648956a4e3a2e019f2bcf"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s12572-018-00243-0"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1112520115"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s12572-018-00243-0", 
      "https://app.dimensions.ai/details/publication/pub.1112520115"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T11:03", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000352_0000000352/records_60354_00000004.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs12572-018-00243-0"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s12572-018-00243-0'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s12572-018-00243-0'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s12572-018-00243-0'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s12572-018-00243-0'


 

This table displays all metadata directly associated to this object as RDF triples.

92 TRIPLES      21 PREDICATES      31 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s12572-018-00243-0 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Naf7093bc1b6f4a9f9e9a851017fa3ff7
4 schema:citation sg:pub.10.1007/978-3-642-03816-7_35
5 sg:pub.10.1007/978-3-642-19094-0_20
6 https://doi.org/10.1016/0012-365x(95)00057-4
7 https://doi.org/10.1016/0020-0190(85)90050-x
8 https://doi.org/10.1016/j.ipl.2007.02.010
9 https://doi.org/10.1142/s0129054107005054
10 https://doi.org/10.4153/cjm-1964-055-5
11 schema:datePublished 2019-03-04
12 schema:datePublishedReg 2019-03-04
13 schema:description A convex bipartite graph G with bipartition (X, Y) and an ordering X=(x1,…,xn) is a bipartite graph such that for each y∈Y, 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’s 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–206, 1985) and Ghosh (in: WALCOM 2011, LNCS 6552, pp. 191–201, 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–298, 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.
14 schema:genre research_article
15 schema:inLanguage en
16 schema:isAccessibleForFree false
17 schema:isPartOf sg:journal.1050051
18 schema:name Hamiltonicity in convex bipartite graphs
19 schema:pagination 1-13
20 schema:productId N1fce844d158b4abcaa575d25eac63f37
21 Na2a77eed931e4a789590d0ab4f42b4a6
22 Ncba7d31bb63b455eaaa804dabaa1b3f7
23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112520115
24 https://doi.org/10.1007/s12572-018-00243-0
25 schema:sdDatePublished 2019-04-11T11:03
26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
27 schema:sdPublisher Nbd8dd2e82e5549c584625f0899de1d8c
28 schema:url https://link.springer.com/10.1007%2Fs12572-018-00243-0
29 sgo:license sg:explorer/license/
30 sgo:sdDataset articles
31 rdf:type schema:ScholarlyArticle
32 N1fce844d158b4abcaa575d25eac63f37 schema:name doi
33 schema:value 10.1007/s12572-018-00243-0
34 rdf:type schema:PropertyValue
35 N2d3c76e7aa684b39b8f3cd0959c25a4a schema:affiliation N9959c39db0684b95b60e9730cf9ab3b0
36 schema:familyName Kowsika
37 schema:givenName P.
38 rdf:type schema:Person
39 N34b108918d614cbeaefa688140ed7625 schema:name Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India
40 rdf:type schema:Organization
41 N6a3253b19c3b4d4ba5da4b92f10d11c3 rdf:first Ncf4908d0c93341f5bc067587fecefa62
42 rdf:rest rdf:nil
43 N931160b6fd5f43379f9ff60dbe967845 schema:affiliation Nb887704c35e14ae4a84b00566d3eda1a
44 schema:familyName Divya
45 schema:givenName V.
46 rdf:type schema:Person
47 N9959c39db0684b95b60e9730cf9ab3b0 schema:name Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India
48 rdf:type schema:Organization
49 Na2a77eed931e4a789590d0ab4f42b4a6 schema:name dimensions_id
50 schema:value pub.1112520115
51 rdf:type schema:PropertyValue
52 Naf7093bc1b6f4a9f9e9a851017fa3ff7 rdf:first N2d3c76e7aa684b39b8f3cd0959c25a4a
53 rdf:rest Ned14496abb2b4130ad14ab597b3b08a7
54 Nb887704c35e14ae4a84b00566d3eda1a schema:name Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India
55 rdf:type schema:Organization
56 Nbd8dd2e82e5549c584625f0899de1d8c schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 Ncba7d31bb63b455eaaa804dabaa1b3f7 schema:name readcube_id
59 schema:value 88b4c17327970b989df188ce2ace0ab0574917b6300648956a4e3a2e019f2bcf
60 rdf:type schema:PropertyValue
61 Ncf4908d0c93341f5bc067587fecefa62 schema:affiliation N34b108918d614cbeaefa688140ed7625
62 schema:familyName Sadagopan
63 schema:givenName N.
64 rdf:type schema:Person
65 Ned14496abb2b4130ad14ab597b3b08a7 rdf:first N931160b6fd5f43379f9ff60dbe967845
66 rdf:rest N6a3253b19c3b4d4ba5da4b92f10d11c3
67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
68 schema:name Information and Computing Sciences
69 rdf:type schema:DefinedTerm
70 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
71 schema:name Computation Theory and Mathematics
72 rdf:type schema:DefinedTerm
73 sg:journal.1050051 schema:issn 0975-0770
74 0975-5616
75 schema:name International Journal of Advances in Engineering Sciences and Applied Mathematics
76 rdf:type schema:Periodical
77 sg:pub.10.1007/978-3-642-03816-7_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034196859
78 https://doi.org/10.1007/978-3-642-03816-7_35
79 rdf:type schema:CreativeWork
80 sg:pub.10.1007/978-3-642-19094-0_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019564675
81 https://doi.org/10.1007/978-3-642-19094-0_20
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1016/0012-365x(95)00057-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019406771
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1016/0020-0190(85)90050-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1011139166
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1016/j.ipl.2007.02.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045057680
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1142/s0129054107005054 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896798
90 rdf:type schema:CreativeWork
91 https://doi.org/10.4153/cjm-1964-055-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072264594
92 rdf:type schema:CreativeWork
 




Preview window. Press ESC to close (or click here)


...