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

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 N7760f3068fdb435c92ca8ec0148edeb1
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 N8a09330bbac14393ac9a09b3d0818239
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf N4c1aeaa7c3884ed1bfe6f1edbd45738f
21 schema:name A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs
22 schema:pagination 191-201
23 schema:productId N27c995991bc84cf7adbf3a34de613135
24 N8b11c1f80af04b989f642819a4d6fd97
25 Nd88a242ba7d94070b0abeae830e8a442
26 schema:publisher N4facc52335524fe5938e9e14115c6491
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 N0515b93d9a0c415a92dcbd2d07ff752f
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 N0515b93d9a0c415a92dcbd2d07ff752f schema:name Springer Nature - SN SciGraph project
37 rdf:type schema:Organization
38 N27c995991bc84cf7adbf3a34de613135 schema:name doi
39 schema:value 10.1007/978-3-642-19094-0_20
40 rdf:type schema:PropertyValue
41 N2e07eeb5fd1e4f6eb52b5fc32bed3633 rdf:first sg:person.010006120612.67
42 rdf:rest N55eb514b139840d1a22c726b2bdd26f2
43 N4c1aeaa7c3884ed1bfe6f1edbd45738f schema:isbn 978-3-642-19093-3
44 978-3-642-19094-0
45 schema:name WALCOM: Algorithms and Computation
46 rdf:type schema:Book
47 N4facc52335524fe5938e9e14115c6491 schema:location Berlin, Heidelberg
48 schema:name Springer Berlin Heidelberg
49 rdf:type schema:Organisation
50 N55eb514b139840d1a22c726b2bdd26f2 rdf:first sg:person.016366027737.61
51 rdf:rest rdf:nil
52 N6e9e7735096b4a05be7cbb44f8ce49c4 schema:familyName Katoh
53 schema:givenName Naoki
54 rdf:type schema:Person
55 N7760f3068fdb435c92ca8ec0148edeb1 rdf:first sg:person.014100435251.88
56 rdf:rest N2e07eeb5fd1e4f6eb52b5fc32bed3633
57 N8a09330bbac14393ac9a09b3d0818239 rdf:first N6e9e7735096b4a05be7cbb44f8ce49c4
58 rdf:rest Na1d542d107334934954825404c709ba5
59 N8b11c1f80af04b989f642819a4d6fd97 schema:name readcube_id
60 schema:value 5d3809e5a35e56ba2b49799b63140c1e7abf4c81c5877c04eec9ca90c9be22a5
61 rdf:type schema:PropertyValue
62 N94709e5d3a3e494eaab69b6f62e98dd6 schema:familyName Kumar
63 schema:givenName Amit
64 rdf:type schema:Person
65 Na1d542d107334934954825404c709ba5 rdf:first N94709e5d3a3e494eaab69b6f62e98dd6
66 rdf:rest rdf:nil
67 Nd88a242ba7d94070b0abeae830e8a442 schema:name dimensions_id
68 schema:value pub.1019564675
69 rdf:type schema:PropertyValue
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)


...