Edge and node searching problems on trees View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1997

AUTHORS

Sheng-Lung Peng , Chin-Wen Ho , Tsan-sheng Hsu , Ming-Tat Ko , Chuan-Yi Tang

ABSTRACT

In this paper, we show that there is a natural correspondence between a tree's edge-search strategy and its node-search strategy. By doing so, we simplify the previous linear time algorithm for determining the edge-search number of a tree, and improve the running time of a previous algorithm for constructing an edge-search strategy (or plan) for a tree containing n vertices from O(n log n) to O(n) time. More... »

PAGES

284-293

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-63357-0
978-3-540-69522-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0045095

DOI

http://dx.doi.org/10.1007/bfb0045095

DIMENSIONS

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


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": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "National Tsing Hua University, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Peng", 
        "givenName": "Sheng-Lung", 
        "id": "sg:person.013531324035.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Central University", 
          "id": "https://www.grid.ac/institutes/grid.37589.30", 
          "name": [
            "National Central University, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ho", 
        "givenName": "Chin-Wen", 
        "id": "sg:person.01203214551.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01203214551.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Academia Sinica", 
          "id": "https://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "Academia Sinica, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hsu", 
        "givenName": "Tsan-sheng", 
        "id": "sg:person.015756766665.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015756766665.55"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Academia Sinica", 
          "id": "https://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "Academia Sinica, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ko", 
        "givenName": "Ming-Tat", 
        "id": "sg:person.07473764745.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07473764745.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "National Tsing Hua University, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tang", 
        "givenName": "Chuan-Yi", 
        "id": "sg:person.01312526135.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "In this paper, we show that there is a natural correspondence between a tree's edge-search strategy and its node-search strategy. By doing so, we simplify the previous linear time algorithm for determining the edge-search number of a tree, and improve the running time of a previous algorithm for constructing an edge-search strategy (or plan) for a tree containing n vertices from O(n log n) to O(n) time.", 
    "editor": [
      {
        "familyName": "Jiang", 
        "givenName": "Tao", 
        "type": "Person"
      }, 
      {
        "familyName": "Lee", 
        "givenName": "D. T.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0045095", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-63357-0", 
        "978-3-540-69522-6"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "name": "Edge and node searching problems on trees", 
    "pagination": "284-293", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0045095"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "db1636b4ed4ad63e5f01d6ca974470db83c6db5d99261a9d5a134d36fc174234"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045993585"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0045095", 
      "https://app.dimensions.ai/details/publication/pub.1045993585"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T18:58", 
    "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/0000000001_0000000264/records_8684_00000079.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/BFb0045095"
  }
]
 

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/bfb0045095'

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/bfb0045095'

Turtle is a human-readable linked data format.

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

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

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


 

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

104 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0045095 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nbbcf174e36a641919727cd5e1c528a2b
4 schema:datePublished 1997
5 schema:datePublishedReg 1997-01-01
6 schema:description In this paper, we show that there is a natural correspondence between a tree's edge-search strategy and its node-search strategy. By doing so, we simplify the previous linear time algorithm for determining the edge-search number of a tree, and improve the running time of a previous algorithm for constructing an edge-search strategy (or plan) for a tree containing n vertices from O(n log n) to O(n) time.
7 schema:editor Ne9a1e24360404e47b8aa9bd89e1df070
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N7578ac19f0eb4b489e0da6a94f8b393c
12 schema:name Edge and node searching problems on trees
13 schema:pagination 284-293
14 schema:productId N25e100604bc143caa203934303ac4a85
15 N7afc61ee38994716ab28f16512c75e0c
16 N89f4892b3d5545069e89fe465f66414a
17 schema:publisher N614f1d249fdf4595a721ec62bb28de91
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045993585
19 https://doi.org/10.1007/bfb0045095
20 schema:sdDatePublished 2019-04-15T18:58
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nd77baafb53ee40f2ac838f88f579f518
23 schema:url http://link.springer.com/10.1007/BFb0045095
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N173cfae00de14d3a8836252e2e710fd3 rdf:first sg:person.01203214551.06
28 rdf:rest N3605e07dc0f74eda9abd942b92aeaac8
29 N25e100604bc143caa203934303ac4a85 schema:name doi
30 schema:value 10.1007/bfb0045095
31 rdf:type schema:PropertyValue
32 N3605e07dc0f74eda9abd942b92aeaac8 rdf:first sg:person.015756766665.55
33 rdf:rest Ne6cfb85524d44dff94bf5bbacf8c9444
34 N425380511da546d4b44601d747bf7f11 schema:familyName Lee
35 schema:givenName D. T.
36 rdf:type schema:Person
37 N614f1d249fdf4595a721ec62bb28de91 schema:location Berlin, Heidelberg
38 schema:name Springer Berlin Heidelberg
39 rdf:type schema:Organisation
40 N6bdede2744ee48e99decf90b773b2f62 schema:familyName Jiang
41 schema:givenName Tao
42 rdf:type schema:Person
43 N7578ac19f0eb4b489e0da6a94f8b393c schema:isbn 978-3-540-63357-0
44 978-3-540-69522-6
45 schema:name Computing and Combinatorics
46 rdf:type schema:Book
47 N7afc61ee38994716ab28f16512c75e0c schema:name dimensions_id
48 schema:value pub.1045993585
49 rdf:type schema:PropertyValue
50 N89f4892b3d5545069e89fe465f66414a schema:name readcube_id
51 schema:value db1636b4ed4ad63e5f01d6ca974470db83c6db5d99261a9d5a134d36fc174234
52 rdf:type schema:PropertyValue
53 Nbbcf174e36a641919727cd5e1c528a2b rdf:first sg:person.013531324035.31
54 rdf:rest N173cfae00de14d3a8836252e2e710fd3
55 Ncb162d53b1064782a91b390434483807 rdf:first N425380511da546d4b44601d747bf7f11
56 rdf:rest rdf:nil
57 Nd77baafb53ee40f2ac838f88f579f518 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 Ne6cfb85524d44dff94bf5bbacf8c9444 rdf:first sg:person.07473764745.12
60 rdf:rest Ne9f2526ecb0048c1a86687eaf7822bbe
61 Ne9a1e24360404e47b8aa9bd89e1df070 rdf:first N6bdede2744ee48e99decf90b773b2f62
62 rdf:rest Ncb162d53b1064782a91b390434483807
63 Ne9f2526ecb0048c1a86687eaf7822bbe rdf:first sg:person.01312526135.27
64 rdf:rest rdf:nil
65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
66 schema:name Information and Computing Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
69 schema:name Computation Theory and Mathematics
70 rdf:type schema:DefinedTerm
71 sg:person.01203214551.06 schema:affiliation https://www.grid.ac/institutes/grid.37589.30
72 schema:familyName Ho
73 schema:givenName Chin-Wen
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01203214551.06
75 rdf:type schema:Person
76 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
77 schema:familyName Tang
78 schema:givenName Chuan-Yi
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
80 rdf:type schema:Person
81 sg:person.013531324035.31 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
82 schema:familyName Peng
83 schema:givenName Sheng-Lung
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31
85 rdf:type schema:Person
86 sg:person.015756766665.55 schema:affiliation https://www.grid.ac/institutes/grid.28665.3f
87 schema:familyName Hsu
88 schema:givenName Tsan-sheng
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015756766665.55
90 rdf:type schema:Person
91 sg:person.07473764745.12 schema:affiliation https://www.grid.ac/institutes/grid.28665.3f
92 schema:familyName Ko
93 schema:givenName Ming-Tat
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07473764745.12
95 rdf:type schema:Person
96 https://www.grid.ac/institutes/grid.28665.3f schema:alternateName Academia Sinica
97 schema:name Academia Sinica, Taiwan
98 rdf:type schema:Organization
99 https://www.grid.ac/institutes/grid.37589.30 schema:alternateName National Central University
100 schema:name National Central University, Taiwan
101 rdf:type schema:Organization
102 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
103 schema:name National Tsing Hua University, Taiwan
104 rdf:type schema:Organization
 




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


...