The Longest Path Problem is Polynomial on Cocomparability Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Kyriaki Ioannidou , Stavros D. Nikolopoulos

ABSTRACT

The longest path problem is the problem of finding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago[9], the complexity status of the longest path problem on cocomparability graphs has remained open until now; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs[18] and provides polynomial solution to the class of permutation graphs. More... »

PAGES

27-38

References to SciGraph publications

Book

TITLE

Graph Theoretic Concepts in Computer Science

ISBN

978-3-642-16925-0
978-3-642-16926-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-16926-7_5

DOI

http://dx.doi.org/10.1007/978-3-642-16926-7_5

DIMENSIONS

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


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": "University of Ioannina", 
          "id": "https://www.grid.ac/institutes/grid.9594.1", 
          "name": [
            "Department of Computer Science, University of Ioannina, GR-45110, Ioannina, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ioannidou", 
        "givenName": "Kyriaki", 
        "id": "sg:person.07355624061.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07355624061.11"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Ioannina", 
          "id": "https://www.grid.ac/institutes/grid.9594.1", 
          "name": [
            "Department of Computer Science, University of Ioannina, GR-45110, Ioannina, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nikolopoulos", 
        "givenName": "Stavros D.", 
        "id": "sg:person.011724474746.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724474746.51"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s00453-009-9292-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005875952", 
          "https://doi.org/10.1007/s00453-009-9292-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-009-9292-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005875952", 
          "https://doi.org/10.1007/s00453-009-9292-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-77891-2_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012923170", 
          "https://doi.org/10.1007/978-3-540-77891-2_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-77891-2_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012923170", 
          "https://doi.org/10.1007/978-3-540-77891-2_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2007.02.012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016217375"
        ], 
        "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": "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": "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": "https://doi.org/10.1145/1007352.1007418", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025270745"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00571188", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025398696", 
          "https://doi.org/10.1007/bf00571188"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00571188", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025398696", 
          "https://doi.org/10.1007/bf00571188"
        ], 
        "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/0020-0190(89)90038-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034568232"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/(sici)1097-0037(199908)34:1<1::aid-net1>3.0.co;2-c", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035398798"
        ], 
        "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": "sg:pub.10.1007/bf00337617", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039152937", 
          "https://doi.org/10.1007/bf00337617"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00337617", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039152937", 
          "https://doi.org/10.1007/bf00337617"
        ], 
        "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": "sg:pub.10.1007/978-3-540-92182-0_66", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045644398", 
          "https://doi.org/10.1007/978-3-540-92182-0_66"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-92182-0_66", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045644398", 
          "https://doi.org/10.1007/978-3-540-92182-0_66"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/ietisy/e91-d.2.170", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059672421"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0205049", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841335"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0211056", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841672"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539791200375", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879670"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9780898719796", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098557270"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9780898719802", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098557271"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "The longest path problem is the problem of finding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago[9], the complexity status of the longest path problem on cocomparability graphs has remained open until now; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs[18] and provides polynomial solution to the class of permutation graphs.", 
    "editor": [
      {
        "familyName": "Thilikos", 
        "givenName": "Dimitrios M.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-16926-7_5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-16925-0", 
        "978-3-642-16926-7"
      ], 
      "name": "Graph Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "name": "The Longest Path Problem is Polynomial on Cocomparability Graphs", 
    "pagination": "27-38", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1023077634"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-16926-7_5"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "6df25a85133887aa2c82f115937f900e02544a49bcfd55fa7ae017b24036604d"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-16926-7_5", 
      "https://app.dimensions.ai/details/publication/pub.1023077634"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:33", 
    "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/0000000364_0000000364/records_72869_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-16926-7_5"
  }
]
 

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-16926-7_5'

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-16926-7_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16926-7_5'

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-16926-7_5'


 

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

151 TRIPLES      23 PREDICATES      51 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-16926-7_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N0e26024663bb4cd6af24af8f33cb0aaa
4 schema:citation sg:pub.10.1007/978-3-540-30551-4_74
5 sg:pub.10.1007/978-3-540-77891-2_3
6 sg:pub.10.1007/978-3-540-92182-0_66
7 sg:pub.10.1007/978-3-642-03816-7_35
8 sg:pub.10.1007/bf00337617
9 sg:pub.10.1007/bf00571188
10 sg:pub.10.1007/s00453-009-9292-5
11 https://doi.org/10.1002/(sici)1097-0037(199908)34:1<1::aid-net1>3.0.co;2-c
12 https://doi.org/10.1016/0012-365x(93)90223-g
13 https://doi.org/10.1016/0012-365x(95)00057-4
14 https://doi.org/10.1016/0020-0190(83)90078-9
15 https://doi.org/10.1016/0020-0190(89)90038-0
16 https://doi.org/10.1016/0020-0190(89)90059-8
17 https://doi.org/10.1016/0020-0190(90)90064-5
18 https://doi.org/10.1016/j.ipl.2007.02.010
19 https://doi.org/10.1016/j.tcs.2007.02.012
20 https://doi.org/10.1016/s0020-0190(01)00198-3
21 https://doi.org/10.1093/ietisy/e91-d.2.170
22 https://doi.org/10.1137/0205049
23 https://doi.org/10.1137/0211056
24 https://doi.org/10.1137/1.9780898719796
25 https://doi.org/10.1137/1.9780898719802
26 https://doi.org/10.1137/s0097539791200375
27 https://doi.org/10.1145/1007352.1007418
28 schema:datePublished 2010
29 schema:datePublishedReg 2010-01-01
30 schema:description The longest path problem is the problem of finding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago[9], the complexity status of the longest path problem on cocomparability graphs has remained open until now; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs[18] and provides polynomial solution to the class of permutation graphs.
31 schema:editor Nbe782d7cdf94415db973af72fcb73c5b
32 schema:genre chapter
33 schema:inLanguage en
34 schema:isAccessibleForFree true
35 schema:isPartOf N28cef510fd314911a9fdc7e19d382aee
36 schema:name The Longest Path Problem is Polynomial on Cocomparability Graphs
37 schema:pagination 27-38
38 schema:productId N62c9d9f1b7694744a80426887659f2ee
39 N7f9a79935ee9481ebd65ef9da412e95c
40 Ne62ec4882c4a44d7a4dfe3c66d45bdef
41 schema:publisher Nac12d649d85445a5998c384a9edf2468
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023077634
43 https://doi.org/10.1007/978-3-642-16926-7_5
44 schema:sdDatePublished 2019-04-16T08:33
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher N227caf28e335409ab62460299d139afa
47 schema:url https://link.springer.com/10.1007%2F978-3-642-16926-7_5
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N0e26024663bb4cd6af24af8f33cb0aaa rdf:first sg:person.07355624061.11
52 rdf:rest N77551b0c7cb84746a89308146b8fce15
53 N227caf28e335409ab62460299d139afa schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 N28cef510fd314911a9fdc7e19d382aee schema:isbn 978-3-642-16925-0
56 978-3-642-16926-7
57 schema:name Graph Theoretic Concepts in Computer Science
58 rdf:type schema:Book
59 N62c9d9f1b7694744a80426887659f2ee schema:name dimensions_id
60 schema:value pub.1023077634
61 rdf:type schema:PropertyValue
62 N6e674f965b704a838cfeac566c8ce8c5 schema:familyName Thilikos
63 schema:givenName Dimitrios M.
64 rdf:type schema:Person
65 N77551b0c7cb84746a89308146b8fce15 rdf:first sg:person.011724474746.51
66 rdf:rest rdf:nil
67 N7f9a79935ee9481ebd65ef9da412e95c schema:name readcube_id
68 schema:value 6df25a85133887aa2c82f115937f900e02544a49bcfd55fa7ae017b24036604d
69 rdf:type schema:PropertyValue
70 Nac12d649d85445a5998c384a9edf2468 schema:location Berlin, Heidelberg
71 schema:name Springer Berlin Heidelberg
72 rdf:type schema:Organisation
73 Nbe782d7cdf94415db973af72fcb73c5b rdf:first N6e674f965b704a838cfeac566c8ce8c5
74 rdf:rest rdf:nil
75 Ne62ec4882c4a44d7a4dfe3c66d45bdef schema:name doi
76 schema:value 10.1007/978-3-642-16926-7_5
77 rdf:type schema:PropertyValue
78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
79 schema:name Information and Computing Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
82 schema:name Computation Theory and Mathematics
83 rdf:type schema:DefinedTerm
84 sg:person.011724474746.51 schema:affiliation https://www.grid.ac/institutes/grid.9594.1
85 schema:familyName Nikolopoulos
86 schema:givenName Stavros D.
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724474746.51
88 rdf:type schema:Person
89 sg:person.07355624061.11 schema:affiliation https://www.grid.ac/institutes/grid.9594.1
90 schema:familyName Ioannidou
91 schema:givenName Kyriaki
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07355624061.11
93 rdf:type schema:Person
94 sg:pub.10.1007/978-3-540-30551-4_74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021479036
95 https://doi.org/10.1007/978-3-540-30551-4_74
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/978-3-540-77891-2_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012923170
98 https://doi.org/10.1007/978-3-540-77891-2_3
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/978-3-540-92182-0_66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045644398
101 https://doi.org/10.1007/978-3-540-92182-0_66
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/978-3-642-03816-7_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034196859
104 https://doi.org/10.1007/978-3-642-03816-7_35
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/bf00337617 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039152937
107 https://doi.org/10.1007/bf00337617
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/bf00571188 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025398696
110 https://doi.org/10.1007/bf00571188
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/s00453-009-9292-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005875952
113 https://doi.org/10.1007/s00453-009-9292-5
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1002/(sici)1097-0037(199908)34:1<1::aid-net1>3.0.co;2-c schema:sameAs https://app.dimensions.ai/details/publication/pub.1035398798
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/0012-365x(93)90223-g schema:sameAs https://app.dimensions.ai/details/publication/pub.1019842874
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1016/0012-365x(95)00057-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019406771
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1016/0020-0190(83)90078-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018477486
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1016/0020-0190(89)90038-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034568232
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1016/0020-0190(89)90059-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037815836
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1016/0020-0190(90)90064-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017022514
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1016/j.ipl.2007.02.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045057680
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1016/j.tcs.2007.02.012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016217375
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1016/s0020-0190(01)00198-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038695986
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1093/ietisy/e91-d.2.170 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059672421
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1137/0205049 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841335
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1137/0211056 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841672
140 rdf:type schema:CreativeWork
141 https://doi.org/10.1137/1.9780898719796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557270
142 rdf:type schema:CreativeWork
143 https://doi.org/10.1137/1.9780898719802 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557271
144 rdf:type schema:CreativeWork
145 https://doi.org/10.1137/s0097539791200375 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879670
146 rdf:type schema:CreativeWork
147 https://doi.org/10.1145/1007352.1007418 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025270745
148 rdf:type schema:CreativeWork
149 https://www.grid.ac/institutes/grid.9594.1 schema:alternateName University of Ioannina
150 schema:name Department of Computer Science, University of Ioannina, GR-45110, Ioannina, Greece
151 rdf:type schema:Organization
 




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


...