A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Esha Ghosh , N. S. Narayanaswamy , C. Pandu Rangan

ABSTRACT

The longest path problem is the problem of finding a simple path of maximum length in a graph. Polynomial solutions for this problem are known only for special classes of graphs, while it is NP-hard on general graphs. In this paper we are proposing a O(n6) time algorithm to find the longest path on biconvex graphs, where n is the number of vertices of the input graph. We have used Dynamic Programming approach. More... »

PAGES

191-201

References to SciGraph publications

  • 2009. The Longest Path Problem Is Polynomial on Interval Graphs in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009
  • 2010. The Longest Path Problem is Polynomial on Cocomparability Graphs in GRAPH THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 2004. Efficient Algorithms for the Longest Path Problem in ALGORITHMS AND COMPUTATION
  • Book

    TITLE

    WALCOM: Algorithms and Computation

    ISBN

    978-3-642-19093-3
    978-3-642-19094-0

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-19094-0_20

    DOI

    http://dx.doi.org/10.1007/978-3-642-19094-0_20

    DIMENSIONS

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


    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": {
              "alternateName": "Indian Institute of Technology Madras", 
              "id": "https://www.grid.ac/institutes/grid.417969.4", 
              "name": [
                "Dept. of Computer Science and Engineering, IIT Madras, 600036, Chennai, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ghosh", 
            "givenName": "Esha", 
            "id": "sg:person.014100435251.88", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014100435251.88"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Indian Institute of Technology Madras", 
              "id": "https://www.grid.ac/institutes/grid.417969.4", 
              "name": [
                "Dept. of Computer Science and Engineering, IIT Madras, 600036, Chennai, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Narayanaswamy", 
            "givenName": "N. S.", 
            "id": "sg:person.010006120612.67", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010006120612.67"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Indian Institute of Technology Madras", 
              "id": "https://www.grid.ac/institutes/grid.417969.4", 
              "name": [
                "Dept. of Computer Science and Engineering, IIT Madras, 600036, Chennai, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rangan", 
            "givenName": "C. Pandu", 
            "id": "sg:person.016366027737.61", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/s0166-218x(99)00217-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002668754"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(90)90064-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017022514"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30551-4_74", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021479036", 
              "https://doi.org/10.1007/978-3-540-30551-4_74"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30551-4_74", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021479036", 
              "https://doi.org/10.1007/978-3-540-30551-4_74"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-16926-7_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023077634", 
              "https://doi.org/10.1007/978-3-642-16926-7_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-16926-7_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023077634", 
              "https://doi.org/10.1007/978-3-642-16926-7_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0166-218x(87)80003-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032649662"
            ], 
            "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.1137/1.9780898719796", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098557270"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2011", 
        "datePublishedReg": "2011-01-01", 
        "description": "The longest path problem is the problem of finding a simple path of maximum length in a graph. Polynomial solutions for this problem are known only for special classes of graphs, while it is NP-hard on general graphs. In this paper we are proposing a O(n6) time algorithm to find the longest path on biconvex graphs, where n is the number of vertices of the input graph. We have used Dynamic Programming approach.", 
        "editor": [
          {
            "familyName": "Katoh", 
            "givenName": "Naoki", 
            "type": "Person"
          }, 
          {
            "familyName": "Kumar", 
            "givenName": "Amit", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-19094-0_20", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-19093-3", 
            "978-3-642-19094-0"
          ], 
          "name": "WALCOM: Algorithms and Computation", 
          "type": "Book"
        }, 
        "name": "A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs", 
        "pagination": "191-201", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1019564675"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-19094-0_20"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5d3809e5a35e56ba2b49799b63140c1e7abf4c81c5877c04eec9ca90c9be22a5"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-19094-0_20", 
          "https://app.dimensions.ai/details/publication/pub.1019564675"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:38", 
        "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/0000000365_0000000365/records_71704_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-19094-0_20"
      }
    ]
     

    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/978-3-642-19094-0_20'

    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/978-3-642-19094-0_20'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-19094-0_20'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-19094-0_20'


     

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

    114 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-19094-0_20 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Ne4545ed560eb4efb80d0b09031b58844
    4 schema:citation sg:pub.10.1007/978-3-540-30551-4_74
    5 sg:pub.10.1007/978-3-642-03816-7_35
    6 sg:pub.10.1007/978-3-642-16926-7_5
    7 https://doi.org/10.1016/0020-0190(90)90064-5
    8 https://doi.org/10.1016/j.ipl.2007.02.010
    9 https://doi.org/10.1016/s0166-218x(87)80003-3
    10 https://doi.org/10.1016/s0166-218x(99)00217-6
    11 https://doi.org/10.1137/1.9780898719796
    12 https://doi.org/10.1142/s0129054107005054
    13 schema:datePublished 2011
    14 schema:datePublishedReg 2011-01-01
    15 schema:description The longest path problem is the problem of finding a simple path of maximum length in a graph. Polynomial solutions for this problem are known only for special classes of graphs, while it is NP-hard on general graphs. In this paper we are proposing a O(n6) time algorithm to find the longest path on biconvex graphs, where n is the number of vertices of the input graph. We have used Dynamic Programming approach.
    16 schema:editor N2accbd457651464f84548afb1655decd
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree false
    20 schema:isPartOf N6d7b7dac66134e1faeb47b20f7350314
    21 schema:name A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs
    22 schema:pagination 191-201
    23 schema:productId N0685941acbda4447a3216735cafe6eb8
    24 N1433fe6c07054908864459b2c1df0229
    25 Nde6777faff9a40b39f886276132b1479
    26 schema:publisher N925cd53cf8254acc94bb3b9f7d105738
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019564675
    28 https://doi.org/10.1007/978-3-642-19094-0_20
    29 schema:sdDatePublished 2019-04-16T08:38
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher Nd2c8fe38dc614cf396eca94a1c9cbf27
    32 schema:url https://link.springer.com/10.1007%2F978-3-642-19094-0_20
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N0685941acbda4447a3216735cafe6eb8 schema:name readcube_id
    37 schema:value 5d3809e5a35e56ba2b49799b63140c1e7abf4c81c5877c04eec9ca90c9be22a5
    38 rdf:type schema:PropertyValue
    39 N1433fe6c07054908864459b2c1df0229 schema:name doi
    40 schema:value 10.1007/978-3-642-19094-0_20
    41 rdf:type schema:PropertyValue
    42 N2accbd457651464f84548afb1655decd rdf:first N43195e5ee27f4f318e85bec9136ae291
    43 rdf:rest Nab7f314f6e234c03b8df413376295f8b
    44 N43195e5ee27f4f318e85bec9136ae291 schema:familyName Katoh
    45 schema:givenName Naoki
    46 rdf:type schema:Person
    47 N6203ad63cfc2461d812c8a6fa6b475b0 schema:familyName Kumar
    48 schema:givenName Amit
    49 rdf:type schema:Person
    50 N6d7b7dac66134e1faeb47b20f7350314 schema:isbn 978-3-642-19093-3
    51 978-3-642-19094-0
    52 schema:name WALCOM: Algorithms and Computation
    53 rdf:type schema:Book
    54 N86c88585881541ba8b955f2e479ff071 rdf:first sg:person.010006120612.67
    55 rdf:rest Ne95d499cc2ad43f98807000091257264
    56 N925cd53cf8254acc94bb3b9f7d105738 schema:location Berlin, Heidelberg
    57 schema:name Springer Berlin Heidelberg
    58 rdf:type schema:Organisation
    59 Nab7f314f6e234c03b8df413376295f8b rdf:first N6203ad63cfc2461d812c8a6fa6b475b0
    60 rdf:rest rdf:nil
    61 Nd2c8fe38dc614cf396eca94a1c9cbf27 schema:name Springer Nature - SN SciGraph project
    62 rdf:type schema:Organization
    63 Nde6777faff9a40b39f886276132b1479 schema:name dimensions_id
    64 schema:value pub.1019564675
    65 rdf:type schema:PropertyValue
    66 Ne4545ed560eb4efb80d0b09031b58844 rdf:first sg:person.014100435251.88
    67 rdf:rest N86c88585881541ba8b955f2e479ff071
    68 Ne95d499cc2ad43f98807000091257264 rdf:first sg:person.016366027737.61
    69 rdf:rest rdf:nil
    70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Information and Computing Sciences
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Computation Theory and Mathematics
    75 rdf:type schema:DefinedTerm
    76 sg:person.010006120612.67 schema:affiliation https://www.grid.ac/institutes/grid.417969.4
    77 schema:familyName Narayanaswamy
    78 schema:givenName N. S.
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010006120612.67
    80 rdf:type schema:Person
    81 sg:person.014100435251.88 schema:affiliation https://www.grid.ac/institutes/grid.417969.4
    82 schema:familyName Ghosh
    83 schema:givenName Esha
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014100435251.88
    85 rdf:type schema:Person
    86 sg:person.016366027737.61 schema:affiliation https://www.grid.ac/institutes/grid.417969.4
    87 schema:familyName Rangan
    88 schema:givenName C. Pandu
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61
    90 rdf:type schema:Person
    91 sg:pub.10.1007/978-3-540-30551-4_74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021479036
    92 https://doi.org/10.1007/978-3-540-30551-4_74
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/978-3-642-03816-7_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034196859
    95 https://doi.org/10.1007/978-3-642-03816-7_35
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/978-3-642-16926-7_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023077634
    98 https://doi.org/10.1007/978-3-642-16926-7_5
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/0020-0190(90)90064-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017022514
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/j.ipl.2007.02.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045057680
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/s0166-218x(87)80003-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032649662
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/s0166-218x(99)00217-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002668754
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1137/1.9780898719796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557270
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1142/s0129054107005054 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896798
    111 rdf:type schema:CreativeWork
    112 https://www.grid.ac/institutes/grid.417969.4 schema:alternateName Indian Institute of Technology Madras
    113 schema:name Dept. of Computer Science and Engineering, IIT Madras, 600036, Chennai, India
    114 rdf:type schema:Organization
     




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


    ...