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 N3fe3ec3986a84f829d297dcf53d31f04
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 Nb51dd957939d4097807f4fb37dc58549
28 schema:genre chapter
29 schema:inLanguage en
30 schema:isAccessibleForFree false
31 schema:isPartOf N3cf75bf53039431b9646beb872562292
32 schema:name Efficient Algorithms for the Longest Path Problem
33 schema:pagination 871-883
34 schema:productId N7da6c484102c45c3bafd9388fa5548dd
35 N969e63d95f684d989b7cad4dd16122b9
36 Nd86fcff43bfd43e195e39288dd27e867
37 schema:publisher N23d5b0215b354ecdaf7f6892d161b99f
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 N9b171a5772ce4b7e954a97ea15b25c8c
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 N1a791d97d48f43d4ac379b4e174d1d19 rdf:first sg:person.016070367373.00
48 rdf:rest rdf:nil
49 N23d5b0215b354ecdaf7f6892d161b99f schema:location Berlin, Heidelberg
50 schema:name Springer Berlin Heidelberg
51 rdf:type schema:Organisation
52 N3cf75bf53039431b9646beb872562292 schema:isbn 978-3-540-24131-7
53 978-3-540-30551-4
54 schema:name Algorithms and Computation
55 rdf:type schema:Book
56 N3fe3ec3986a84f829d297dcf53d31f04 rdf:first sg:person.011467765731.43
57 rdf:rest N1a791d97d48f43d4ac379b4e174d1d19
58 N7da6c484102c45c3bafd9388fa5548dd schema:name dimensions_id
59 schema:value pub.1021479036
60 rdf:type schema:PropertyValue
61 N969e63d95f684d989b7cad4dd16122b9 schema:name readcube_id
62 schema:value 6656406b13d8317ffeb157c161f95ff9d87c4edfc175b4010a167b9aeee876a1
63 rdf:type schema:PropertyValue
64 N9b171a5772ce4b7e954a97ea15b25c8c schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 Nb51dd957939d4097807f4fb37dc58549 rdf:first Nc103fefac7d947b9ba6a26cd4f60c73b
67 rdf:rest Nd8d9ccc30a02489c819df15681baa2de
68 Nc103fefac7d947b9ba6a26cd4f60c73b schema:familyName Fleischer
69 schema:givenName Rudolf
70 rdf:type schema:Person
71 Nc445408ccd1c49cdb17963ca6713c55c schema:familyName Trippen
72 schema:givenName Gerhard
73 rdf:type schema:Person
74 Nd86fcff43bfd43e195e39288dd27e867 schema:name doi
75 schema:value 10.1007/978-3-540-30551-4_74
76 rdf:type schema:PropertyValue
77 Nd8d9ccc30a02489c819df15681baa2de rdf:first Nc445408ccd1c49cdb17963ca6713c55c
78 rdf:rest rdf:nil
79 Nf3189a788f3640dbb910a4e3a4f7075c 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 Nf3189a788f3640dbb910a4e3a4f7075c
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)


...