Efficient Algorithms for the Longest Path Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Ryuhei Uehara , Yushi Uno

ABSTRACT

The longest path problem is to find a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, very few graph classes are known where the longest path problem can be solved efficiently. For a tree, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and it then solves the longest path problem efficiently for weighted trees, block graphs, ptolemaic graphs, and cacti. We next propose three new graph classes that have natural interval representations, and show that the longest path problem can be solved efficiently on those classes. As a corollary, it is also shown that the problem can be solved efficiently on threshold graphs. More... »

PAGES

871-883

Book

TITLE

Algorithms and Computation

ISBN

978-3-540-24131-7
978-3-540-30551-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30551-4_74

DOI

http://dx.doi.org/10.1007/978-3-540-30551-4_74

DIMENSIONS

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


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 Information Processing, School of Information Science, JAIST, Ishikawa, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Uehara", 
        "givenName": "Ryuhei", 
        "id": "sg:person.011467765731.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011467765731.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Osaka Prefecture University", 
          "id": "https://www.grid.ac/institutes/grid.261455.1", 
          "name": [
            "Department of Mathematics and Information Science, College of Integrated Arts and Sciences, Osaka Prefecture University, Sakai, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Uno", 
        "givenName": "Yushi", 
        "id": "sg:person.016070367373.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016070367373.00"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0377-2217(02)00433-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011411066"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(02)00433-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011411066"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/210332.210337", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011509889"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(83)90078-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018477486"
        ], 
        "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": "https://doi.org/10.1016/0012-365x(93)90223-g", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019842874"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(93)e0077-h", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021011097"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-0208(08)73110-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025882287"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1026792740", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-58412-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026792740", 
          "https://doi.org/10.1007/978-3-642-58412-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-58412-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026792740", 
          "https://doi.org/10.1007/978-3-642-58412-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(76)80045-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030334487"
        ], 
        "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": "https://doi.org/10.1016/0020-0190(89)90059-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037815836"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0020-0190(01)00198-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038695986"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(86)90135-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045389441"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(86)90135-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045389441"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02523689", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048536748", 
          "https://doi.org/10.1007/bf02523689"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02523689", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048536748", 
          "https://doi.org/10.1007/bf02523689"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1050354225", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-0515-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050354225", 
          "https://doi.org/10.1007/978-1-4612-0515-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-0515-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050354225", 
          "https://doi.org/10.1007/978-1-4612-0515-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0218005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842104"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539702416761", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879409"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9780898719796", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098557270"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "The longest path problem is to find a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, very few graph classes are known where the longest path problem can be solved efficiently. For a tree, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and it then solves the longest path problem efficiently for weighted trees, block graphs, ptolemaic graphs, and cacti. We next propose three new graph classes that have natural interval representations, and show that the longest path problem can be solved efficiently on those classes. As a corollary, it is also shown that the problem can be solved efficiently on threshold graphs.", 
    "editor": [
      {
        "familyName": "Fleischer", 
        "givenName": "Rudolf", 
        "type": "Person"
      }, 
      {
        "familyName": "Trippen", 
        "givenName": "Gerhard", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30551-4_74", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24131-7", 
        "978-3-540-30551-4"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "name": "Efficient Algorithms for the Longest Path Problem", 
    "pagination": "871-883", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021479036"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30551-4_74"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "6656406b13d8317ffeb157c161f95ff9d87c4edfc175b4010a167b9aeee876a1"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30551-4_74", 
      "https://app.dimensions.ai/details/publication/pub.1021479036"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:37", 
    "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_71692_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-30551-4_74"
  }
]
 

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-540-30551-4_74'

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-540-30551-4_74'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30551-4_74'

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-540-30551-4_74'


 

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

140 TRIPLES      23 PREDICATES      47 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30551-4_74 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N45f17a26f682488c9a6bb1df19f0b3b6
4 schema:citation sg:pub.10.1007/978-1-4612-0515-9
5 sg:pub.10.1007/978-3-642-58412-1
6 sg:pub.10.1007/bf02523689
7 https://app.dimensions.ai/details/publication/pub.1026792740
8 https://app.dimensions.ai/details/publication/pub.1050354225
9 https://doi.org/10.1016/0012-365x(93)90223-g
10 https://doi.org/10.1016/0012-365x(93)e0077-h
11 https://doi.org/10.1016/0012-365x(95)00057-4
12 https://doi.org/10.1016/0020-0190(83)90078-9
13 https://doi.org/10.1016/0020-0190(86)90135-3
14 https://doi.org/10.1016/0020-0190(89)90059-8
15 https://doi.org/10.1016/s0020-0190(01)00198-3
16 https://doi.org/10.1016/s0022-0000(76)80045-1
17 https://doi.org/10.1016/s0166-218x(87)80003-3
18 https://doi.org/10.1016/s0304-0208(08)73110-4
19 https://doi.org/10.1016/s0377-2217(02)00433-2
20 https://doi.org/10.1137/0218005
21 https://doi.org/10.1137/1.9780898719796
22 https://doi.org/10.1137/s0097539702416761
23 https://doi.org/10.1145/210332.210337
24 schema:datePublished 2004
25 schema:datePublishedReg 2004-01-01
26 schema:description The longest path problem is to find a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, very few graph classes are known where the longest path problem can be solved efficiently. For a tree, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and it then solves the longest path problem efficiently for weighted trees, block graphs, ptolemaic graphs, and cacti. We next propose three new graph classes that have natural interval representations, and show that the longest path problem can be solved efficiently on those classes. As a corollary, it is also shown that the problem can be solved efficiently on threshold graphs.
27 schema:editor Neddc6955a5054138b0a37061a58bed21
28 schema:genre chapter
29 schema:inLanguage en
30 schema:isAccessibleForFree false
31 schema:isPartOf N021564a30a6e47cb851d7ff73deee12c
32 schema:name Efficient Algorithms for the Longest Path Problem
33 schema:pagination 871-883
34 schema:productId N1e25f7df9dcb4936af688cd0fbfc63f6
35 N83e6fbfb52e9413d9a02368344a15406
36 N940e059563c74369968b694265500aa9
37 schema:publisher N94e8b2ab9cab4d5daf42d8b294696665
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021479036
39 https://doi.org/10.1007/978-3-540-30551-4_74
40 schema:sdDatePublished 2019-04-16T08:37
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher Nb274c65c22a8465db2c5db512fbd1d6d
43 schema:url https://link.springer.com/10.1007%2F978-3-540-30551-4_74
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N021564a30a6e47cb851d7ff73deee12c schema:isbn 978-3-540-24131-7
48 978-3-540-30551-4
49 schema:name Algorithms and Computation
50 rdf:type schema:Book
51 N093a165b7e8845ecb65308eb60de3dba rdf:first sg:person.016070367373.00
52 rdf:rest rdf:nil
53 N1e25f7df9dcb4936af688cd0fbfc63f6 schema:name doi
54 schema:value 10.1007/978-3-540-30551-4_74
55 rdf:type schema:PropertyValue
56 N45f17a26f682488c9a6bb1df19f0b3b6 rdf:first sg:person.011467765731.43
57 rdf:rest N093a165b7e8845ecb65308eb60de3dba
58 N780fbc086da04aafb426ac09510a0cab rdf:first Nd51a2abfece94f2faf437e0245d54469
59 rdf:rest rdf:nil
60 N83e6fbfb52e9413d9a02368344a15406 schema:name readcube_id
61 schema:value 6656406b13d8317ffeb157c161f95ff9d87c4edfc175b4010a167b9aeee876a1
62 rdf:type schema:PropertyValue
63 N940e059563c74369968b694265500aa9 schema:name dimensions_id
64 schema:value pub.1021479036
65 rdf:type schema:PropertyValue
66 N94e8b2ab9cab4d5daf42d8b294696665 schema:location Berlin, Heidelberg
67 schema:name Springer Berlin Heidelberg
68 rdf:type schema:Organisation
69 Nb274c65c22a8465db2c5db512fbd1d6d schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 Nd3788ed311a14fe28a94926f86bfa377 schema:familyName Fleischer
72 schema:givenName Rudolf
73 rdf:type schema:Person
74 Nd51a2abfece94f2faf437e0245d54469 schema:familyName Trippen
75 schema:givenName Gerhard
76 rdf:type schema:Person
77 Neddc6955a5054138b0a37061a58bed21 rdf:first Nd3788ed311a14fe28a94926f86bfa377
78 rdf:rest N780fbc086da04aafb426ac09510a0cab
79 Nfb1636c76c4b44f3ad37f8381fdf9f49 schema:name Department of Information Processing, School of Information Science, JAIST, Ishikawa, Japan
80 rdf:type schema:Organization
81 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information and Computing Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
85 schema:name Computation Theory and Mathematics
86 rdf:type schema:DefinedTerm
87 sg:person.011467765731.43 schema:affiliation Nfb1636c76c4b44f3ad37f8381fdf9f49
88 schema:familyName Uehara
89 schema:givenName Ryuhei
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011467765731.43
91 rdf:type schema:Person
92 sg:person.016070367373.00 schema:affiliation https://www.grid.ac/institutes/grid.261455.1
93 schema:familyName Uno
94 schema:givenName Yushi
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016070367373.00
96 rdf:type schema:Person
97 sg:pub.10.1007/978-1-4612-0515-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050354225
98 https://doi.org/10.1007/978-1-4612-0515-9
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/978-3-642-58412-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026792740
101 https://doi.org/10.1007/978-3-642-58412-1
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/bf02523689 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048536748
104 https://doi.org/10.1007/bf02523689
105 rdf:type schema:CreativeWork
106 https://app.dimensions.ai/details/publication/pub.1026792740 schema:CreativeWork
107 https://app.dimensions.ai/details/publication/pub.1050354225 schema:CreativeWork
108 https://doi.org/10.1016/0012-365x(93)90223-g schema:sameAs https://app.dimensions.ai/details/publication/pub.1019842874
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0012-365x(93)e0077-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1021011097
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0012-365x(95)00057-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019406771
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/0020-0190(83)90078-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018477486
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/0020-0190(86)90135-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045389441
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1016/0020-0190(89)90059-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037815836
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1016/s0020-0190(01)00198-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038695986
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1016/s0022-0000(76)80045-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030334487
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1016/s0166-218x(87)80003-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032649662
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1016/s0304-0208(08)73110-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025882287
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1016/s0377-2217(02)00433-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011411066
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1137/0218005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842104
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1137/1.9780898719796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557270
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1137/s0097539702416761 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879409
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1145/210332.210337 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011509889
137 rdf:type schema:CreativeWork
138 https://www.grid.ac/institutes/grid.261455.1 schema:alternateName Osaka Prefecture University
139 schema:name Department of Mathematics and Information Science, College of Integrated Arts and Sciences, Osaka Prefecture University, Sakai, Japan
140 rdf:type schema:Organization
 




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


...