Tree Exploration with an Oracle View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Pierre Fraigniaud , David Ilcinkas , Andrzej Pelc

ABSTRACT

We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of particular items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is quantitative: we investigate the minimum number of bits of information (minimum oracle size) that has to be given to an algorithm in order to perform a task with given efficiency. We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm is measured by its competitive ratio, i.e., by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value. We determine the minimum number of bits of information that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold oracle size that turns out to be roughly loglogD, where D is the diameter of the tree. More precisely, for any constant c, we construct an exploration algorithm with competitive ratio smaller than 2, using an oracle of size at most loglogD –c, and we show that every algorithm using an oracle of size loglogD –g(D), for any function g unbounded from above, has competitive ratio at least 2. More... »

PAGES

24-37

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11821069_2

DOI

http://dx.doi.org/10.1007/11821069_2

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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": "French National Centre for Scientific Research", 
          "id": "https://www.grid.ac/institutes/grid.4444.0", 
          "name": [
            "CNRS, Laboratoire de Recherche en Informatique (LRI), Universit\u00e9 Paris-Sud, 91405, Orsay, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fraigniaud", 
        "givenName": "Pierre", 
        "id": "sg:person.013424402135.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratoire de Recherche en Informatique", 
          "id": "https://www.grid.ac/institutes/grid.464180.f", 
          "name": [
            "Laboratoire de Recherche en Informatique (LRI), Universit\u00e9 Paris-Sud, 91405, Orsay, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ilcinkas", 
        "givenName": "David", 
        "id": "sg:person.010032333055.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010032333055.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universit\u00e9 du Qu\u00e9bec en Outaouais", 
          "id": "https://www.grid.ac/institutes/grid.265705.3", 
          "name": [
            "D\u00e9partement d\u2019informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, J8X 3X7, Gatineau, Qu\u00e9bec, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pelc", 
        "givenName": "Andrzej", 
        "id": "sg:person.013306156242.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013306156242.32"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/1073814.1073840", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000991058"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2004.07.031", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001736746"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1146381.1146410", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005207210"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010742782"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/274787.274788", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010783463"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011710285", 
          "https://doi.org/10.1007/11561071_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011710285", 
          "https://doi.org/10.1007/11561071_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011710285", 
          "https://doi.org/10.1007/11561071_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1994.1039", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011760566"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1999.1043", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014281330"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/72981.72982", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016741552"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00446-003-0091-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018732233", 
          "https://doi.org/10.1007/s00446-003-0091-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00993411", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025737737", 
          "https://doi.org/10.1007/bf00993411"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/1097-0037(200009)36:2<96::aid-net4>3.0.co;2-n", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039259679"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jalgor.2003.10.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045412441"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00446-006-0007-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049726567", 
          "https://doi.org/10.1007/s00446-006-0007-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00446-006-0007-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049726567", 
          "https://doi.org/10.1007/s00446-006-0007-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(91)90263-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050621281"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/inco.2001.3081", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052134892"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/70.105395", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061215884"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/70.508436", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061216296"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/71.481599", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061217493"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539791194931", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879656"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s009753979732428x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880193"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1994.365703", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093260501"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2003.1238222", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095694552"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of particular items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is quantitative: we investigate the minimum number of bits of information (minimum oracle size) that has to be given to an algorithm in order to perform a task with given efficiency. We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm is measured by its competitive ratio, i.e., by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value. We determine the minimum number of bits of information that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold oracle size that turns out to be roughly loglogD, where D is the diameter of the tree. More precisely, for any constant c, we construct an exploration algorithm with competitive ratio smaller than 2, using an oracle of size at most loglogD \u2013c, and we show that every algorithm using an oracle of size loglogD \u2013g(D), for any function g unbounded from above, has competitive ratio at least 2.", 
    "editor": [
      {
        "familyName": "Kr\u00e1lovi\u010d", 
        "givenName": "Rastislav", 
        "type": "Person"
      }, 
      {
        "familyName": "Urzyczyn", 
        "givenName": "Pawe\u0142", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11821069_2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-37791-7", 
        "978-3-540-37793-1"
      ], 
      "name": "Mathematical Foundations of Computer Science 2006", 
      "type": "Book"
    }, 
    "name": "Tree Exploration with an Oracle", 
    "pagination": "24-37", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037978405"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11821069_2"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b4ea9a7caf70773e12af03d4833f5bdc676101403a9a88db84122b4d8a55aadb"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11821069_2", 
      "https://app.dimensions.ai/details/publication/pub.1037978405"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:31", 
    "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_72836_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11821069_2"
  }
]
 

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/11821069_2'

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/11821069_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11821069_2'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11821069_2'


 

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

163 TRIPLES      23 PREDICATES      50 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11821069_2 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N81e7f3b76bcf40f1911959b4815d0714
4 schema:citation sg:pub.10.1007/11561071_4
5 sg:pub.10.1007/bf00993411
6 sg:pub.10.1007/s00446-003-0091-y
7 sg:pub.10.1007/s00446-006-0007-8
8 https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8
9 https://doi.org/10.1002/1097-0037(200009)36:2<96::aid-net4>3.0.co;2-n
10 https://doi.org/10.1006/inco.2001.3081
11 https://doi.org/10.1006/jagm.1994.1039
12 https://doi.org/10.1006/jagm.1999.1043
13 https://doi.org/10.1016/0304-3975(91)90263-2
14 https://doi.org/10.1016/j.jalgor.2003.10.002
15 https://doi.org/10.1016/j.tcs.2004.07.031
16 https://doi.org/10.1109/70.105395
17 https://doi.org/10.1109/70.508436
18 https://doi.org/10.1109/71.481599
19 https://doi.org/10.1109/sfcs.1994.365703
20 https://doi.org/10.1109/sfcs.2003.1238222
21 https://doi.org/10.1137/s0097539791194931
22 https://doi.org/10.1137/s009753979732428x
23 https://doi.org/10.1145/1073814.1073840
24 https://doi.org/10.1145/1146381.1146410
25 https://doi.org/10.1145/274787.274788
26 https://doi.org/10.1145/72981.72982
27 schema:datePublished 2006
28 schema:datePublishedReg 2006-01-01
29 schema:description We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of particular items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is quantitative: we investigate the minimum number of bits of information (minimum oracle size) that has to be given to an algorithm in order to perform a task with given efficiency. We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm is measured by its competitive ratio, i.e., by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value. We determine the minimum number of bits of information that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold oracle size that turns out to be roughly loglogD, where D is the diameter of the tree. More precisely, for any constant c, we construct an exploration algorithm with competitive ratio smaller than 2, using an oracle of size at most loglogD –c, and we show that every algorithm using an oracle of size loglogD –g(D), for any function g unbounded from above, has competitive ratio at least 2.
30 schema:editor Nc750be3e22d74b819dca92c764f17c0a
31 schema:genre chapter
32 schema:inLanguage en
33 schema:isAccessibleForFree false
34 schema:isPartOf N076c4ba9ebec4af590144c5e9cb5c8ab
35 schema:name Tree Exploration with an Oracle
36 schema:pagination 24-37
37 schema:productId N2df0be29a19f421d942105058585d1c3
38 N861dab1c5fdc4185a91f447a4cb4ed31
39 Nf572ab9bdec9447cb7b7ac97377738a6
40 schema:publisher N3b094dbf721241d2917c2738406ccd30
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037978405
42 https://doi.org/10.1007/11821069_2
43 schema:sdDatePublished 2019-04-16T08:31
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N52c8c35513154eab87752d13633ec0b3
46 schema:url https://link.springer.com/10.1007%2F11821069_2
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N076c4ba9ebec4af590144c5e9cb5c8ab schema:isbn 978-3-540-37791-7
51 978-3-540-37793-1
52 schema:name Mathematical Foundations of Computer Science 2006
53 rdf:type schema:Book
54 N1281b3b11baa43fd8700eda866cf2575 schema:familyName Urzyczyn
55 schema:givenName Paweł
56 rdf:type schema:Person
57 N2d1eae305b1947709c40d9f6623ae11d rdf:first sg:person.013306156242.32
58 rdf:rest rdf:nil
59 N2df0be29a19f421d942105058585d1c3 schema:name doi
60 schema:value 10.1007/11821069_2
61 rdf:type schema:PropertyValue
62 N3b094dbf721241d2917c2738406ccd30 schema:location Berlin, Heidelberg
63 schema:name Springer Berlin Heidelberg
64 rdf:type schema:Organisation
65 N52c8c35513154eab87752d13633ec0b3 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N61026398a7234dfeabea4e5a27985b7e rdf:first sg:person.010032333055.75
68 rdf:rest N2d1eae305b1947709c40d9f6623ae11d
69 N6310df87b7e1467dacf711474a210af1 schema:familyName Královič
70 schema:givenName Rastislav
71 rdf:type schema:Person
72 N81e7f3b76bcf40f1911959b4815d0714 rdf:first sg:person.013424402135.28
73 rdf:rest N61026398a7234dfeabea4e5a27985b7e
74 N861dab1c5fdc4185a91f447a4cb4ed31 schema:name readcube_id
75 schema:value b4ea9a7caf70773e12af03d4833f5bdc676101403a9a88db84122b4d8a55aadb
76 rdf:type schema:PropertyValue
77 Nc750be3e22d74b819dca92c764f17c0a rdf:first N6310df87b7e1467dacf711474a210af1
78 rdf:rest Nf231046c164749dc8dee44b8590060d1
79 Nf231046c164749dc8dee44b8590060d1 rdf:first N1281b3b11baa43fd8700eda866cf2575
80 rdf:rest rdf:nil
81 Nf572ab9bdec9447cb7b7ac97377738a6 schema:name dimensions_id
82 schema:value pub.1037978405
83 rdf:type schema:PropertyValue
84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information and Computing Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
88 schema:name Artificial Intelligence and Image Processing
89 rdf:type schema:DefinedTerm
90 sg:person.010032333055.75 schema:affiliation https://www.grid.ac/institutes/grid.464180.f
91 schema:familyName Ilcinkas
92 schema:givenName David
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010032333055.75
94 rdf:type schema:Person
95 sg:person.013306156242.32 schema:affiliation https://www.grid.ac/institutes/grid.265705.3
96 schema:familyName Pelc
97 schema:givenName Andrzej
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013306156242.32
99 rdf:type schema:Person
100 sg:person.013424402135.28 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
101 schema:familyName Fraigniaud
102 schema:givenName Pierre
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28
104 rdf:type schema:Person
105 sg:pub.10.1007/11561071_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011710285
106 https://doi.org/10.1007/11561071_4
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/bf00993411 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025737737
109 https://doi.org/10.1007/bf00993411
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/s00446-003-0091-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1018732233
112 https://doi.org/10.1007/s00446-003-0091-y
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/s00446-006-0007-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049726567
115 https://doi.org/10.1007/s00446-006-0007-8
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010742782
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1002/1097-0037(200009)36:2<96::aid-net4>3.0.co;2-n schema:sameAs https://app.dimensions.ai/details/publication/pub.1039259679
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1006/inco.2001.3081 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052134892
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1006/jagm.1994.1039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011760566
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1006/jagm.1999.1043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014281330
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1016/0304-3975(91)90263-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050621281
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1016/j.jalgor.2003.10.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045412441
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1016/j.tcs.2004.07.031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001736746
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1109/70.105395 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061215884
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1109/70.508436 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061216296
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1109/71.481599 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061217493
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1109/sfcs.1994.365703 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093260501
140 rdf:type schema:CreativeWork
141 https://doi.org/10.1109/sfcs.2003.1238222 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095694552
142 rdf:type schema:CreativeWork
143 https://doi.org/10.1137/s0097539791194931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879656
144 rdf:type schema:CreativeWork
145 https://doi.org/10.1137/s009753979732428x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880193
146 rdf:type schema:CreativeWork
147 https://doi.org/10.1145/1073814.1073840 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000991058
148 rdf:type schema:CreativeWork
149 https://doi.org/10.1145/1146381.1146410 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005207210
150 rdf:type schema:CreativeWork
151 https://doi.org/10.1145/274787.274788 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010783463
152 rdf:type schema:CreativeWork
153 https://doi.org/10.1145/72981.72982 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016741552
154 rdf:type schema:CreativeWork
155 https://www.grid.ac/institutes/grid.265705.3 schema:alternateName Université du Québec en Outaouais
156 schema:name Département d’informatique, Université du Québec en Outaouais, J8X 3X7, Gatineau, Québec, Canada
157 rdf:type schema:Organization
158 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
159 schema:name CNRS, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud, 91405, Orsay, France
160 rdf:type schema:Organization
161 https://www.grid.ac/institutes/grid.464180.f schema:alternateName Laboratoire de Recherche en Informatique
162 schema:name Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud, 91405, Orsay, France
163 rdf:type schema:Organization
 




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


...