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

References to SciGraph publications

  • 2009. The Longest Path Problem Is Polynomial on Interval Graphs in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009
  • 2011. A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs in WALCOM: ALGORITHMS AND COMPUTATION
  • 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 N9b6818f50c8e4f17a755fd93bc46c82a
    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 N549deaeeafde4dbab621335e709117bc
    21 N873f0746fe6949ed96f8e7841a77e88e
    22 N9ac44602a6494eebbd975b0f24babfc5
    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 N87b5c0e38d634f19a027eeba3d65eed4
    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 N3e383c851e57411ebfb7f440cc45634e schema:affiliation N880fc76544ff43cfba1b2a96661b3fb0
    33 schema:familyName Divya
    34 schema:givenName V.
    35 rdf:type schema:Person
    36 N549deaeeafde4dbab621335e709117bc schema:name dimensions_id
    37 schema:value pub.1112520115
    38 rdf:type schema:PropertyValue
    39 N6b750a4ea06744f688f4193e09a93a43 schema:name Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India
    40 rdf:type schema:Organization
    41 N70cb9371738d452893bf435889f08480 schema:affiliation Ncfd05404f2f34a5a9155c0d220aeff42
    42 schema:familyName Kowsika
    43 schema:givenName P.
    44 rdf:type schema:Person
    45 N873f0746fe6949ed96f8e7841a77e88e schema:name doi
    46 schema:value 10.1007/s12572-018-00243-0
    47 rdf:type schema:PropertyValue
    48 N87b5c0e38d634f19a027eeba3d65eed4 schema:name Springer Nature - SN SciGraph project
    49 rdf:type schema:Organization
    50 N880fc76544ff43cfba1b2a96661b3fb0 schema:name Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India
    51 rdf:type schema:Organization
    52 N95f16a00d982404c9c5a45e43ad84309 rdf:first Nfa37dcf79a3f4f248fe7f3e889ba50cc
    53 rdf:rest rdf:nil
    54 N9ac44602a6494eebbd975b0f24babfc5 schema:name readcube_id
    55 schema:value 88b4c17327970b989df188ce2ace0ab0574917b6300648956a4e3a2e019f2bcf
    56 rdf:type schema:PropertyValue
    57 N9b6818f50c8e4f17a755fd93bc46c82a rdf:first N70cb9371738d452893bf435889f08480
    58 rdf:rest Nfb2ce4c82d20490d980ee6cdd32a42fc
    59 Ncfd05404f2f34a5a9155c0d220aeff42 schema:name Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, India
    60 rdf:type schema:Organization
    61 Nfa37dcf79a3f4f248fe7f3e889ba50cc schema:affiliation N6b750a4ea06744f688f4193e09a93a43
    62 schema:familyName Sadagopan
    63 schema:givenName N.
    64 rdf:type schema:Person
    65 Nfb2ce4c82d20490d980ee6cdd32a42fc rdf:first N3e383c851e57411ebfb7f440cc45634e
    66 rdf:rest N95f16a00d982404c9c5a45e43ad84309
    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)


    ...