A Linear-Time Algorithm for Constructing an Optimal Node-Search Strategy of a Tree View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1998

AUTHORS

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

ABSTRACT

Ellis et al., proposed algorithms (in terms of vertex separation) to compute the node-search number of an n-vertex tree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An open problem is whether the latter can also be done in linear time. In this paper, we solve this open problem by exploring fundamental graph theoretical properties. More... »

PAGES

279-289

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-68535-9_32

DOI

http://dx.doi.org/10.1007/3-540-68535-9_32

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University, Taiwan", 
          "id": "http://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, Taiwan", 
          "id": "http://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, Taiwan", 
          "id": "http://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, Taiwan", 
          "id": "http://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, Taiwan", 
          "id": "http://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": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "Ellis et al., proposed algorithms (in terms of vertex separation) to compute the node-search number of an n-vertex tree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An open problem is whether the latter can also be done in linear time. In this paper, we solve this open problem by exploring fundamental graph theoretical properties.", 
    "editor": [
      {
        "familyName": "Hsu", 
        "givenName": "Wen-Lian", 
        "type": "Person"
      }, 
      {
        "familyName": "Kao", 
        "givenName": "Ming-Yang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-68535-9_32", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64824-6", 
        "978-3-540-68535-7"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "open problem", 
      "linear-time algorithm", 
      "graph theoretical properties", 
      "linear time", 
      "algorithm", 
      "theoretical properties", 
      "tree T", 
      "time", 
      "trees", 
      "strategies", 
      "number", 
      "properties", 
      "problem", 
      "paper", 
      "node-search number", 
      "vertex tree T", 
      "optimal node-search strategy", 
      "node-search strategy", 
      "fundamental graph theoretical properties"
    ], 
    "name": "A Linear-Time Algorithm for Constructing an Optimal Node-Search Strategy of a Tree", 
    "pagination": "279-289", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019837111"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-68535-9_32"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-68535-9_32", 
      "https://app.dimensions.ai/details/publication/pub.1019837111"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:05", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_327.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-68535-9_32"
  }
]
 

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/3-540-68535-9_32'

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/3-540-68535-9_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-68535-9_32'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-68535-9_32'


 

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

118 TRIPLES      23 PREDICATES      45 URIs      38 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-68535-9_32 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N52f9f98ca8e44ae5a2d0a37df4876cb2
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description Ellis et al., proposed algorithms (in terms of vertex separation) to compute the node-search number of an n-vertex tree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An open problem is whether the latter can also be done in linear time. In this paper, we solve this open problem by exploring fundamental graph theoretical properties.
7 schema:editor N586006e0fd3c4539b8aa58d46e3bdbf9
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N9364ee333a994ed082ac1ed14813cbfb
12 schema:keywords algorithm
13 fundamental graph theoretical properties
14 graph theoretical properties
15 linear time
16 linear-time algorithm
17 node-search number
18 node-search strategy
19 number
20 open problem
21 optimal node-search strategy
22 paper
23 problem
24 properties
25 strategies
26 theoretical properties
27 time
28 tree T
29 trees
30 vertex tree T
31 schema:name A Linear-Time Algorithm for Constructing an Optimal Node-Search Strategy of a Tree
32 schema:pagination 279-289
33 schema:productId N2f7cb76042254c8fb178b50e77fe8243
34 N6af80308fffe42fd956fdf39b04f5ae5
35 schema:publisher N14aecb9e0082436882a8f498945ab763
36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019837111
37 https://doi.org/10.1007/3-540-68535-9_32
38 schema:sdDatePublished 2021-12-01T20:05
39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
40 schema:sdPublisher Ne0e8b8a4399f43529635c5642bd95b66
41 schema:url https://doi.org/10.1007/3-540-68535-9_32
42 sgo:license sg:explorer/license/
43 sgo:sdDataset chapters
44 rdf:type schema:Chapter
45 N090f939a396f481696485a958edda554 schema:familyName Hsu
46 schema:givenName Wen-Lian
47 rdf:type schema:Person
48 N14aecb9e0082436882a8f498945ab763 schema:name Springer Nature
49 rdf:type schema:Organisation
50 N2f7cb76042254c8fb178b50e77fe8243 schema:name doi
51 schema:value 10.1007/3-540-68535-9_32
52 rdf:type schema:PropertyValue
53 N3958ec5107924043a638bab448ec2ddf rdf:first sg:person.07473764745.12
54 rdf:rest N918dda027da44b3ea2532d6327321104
55 N52f9f98ca8e44ae5a2d0a37df4876cb2 rdf:first sg:person.013531324035.31
56 rdf:rest Nc3da072fefba477e913ef6fd88755411
57 N586006e0fd3c4539b8aa58d46e3bdbf9 rdf:first N090f939a396f481696485a958edda554
58 rdf:rest Nf4da353c265749948e7e75a17af214b9
59 N6af80308fffe42fd956fdf39b04f5ae5 schema:name dimensions_id
60 schema:value pub.1019837111
61 rdf:type schema:PropertyValue
62 N918dda027da44b3ea2532d6327321104 rdf:first sg:person.01312526135.27
63 rdf:rest rdf:nil
64 N9364ee333a994ed082ac1ed14813cbfb schema:isbn 978-3-540-64824-6
65 978-3-540-68535-7
66 schema:name Computing and Combinatorics
67 rdf:type schema:Book
68 N9c5319fabb724842a3493c710bab5764 rdf:first sg:person.015756766665.55
69 rdf:rest N3958ec5107924043a638bab448ec2ddf
70 Na250bafef9d346cdac395c2146293e0b schema:familyName Kao
71 schema:givenName Ming-Yang
72 rdf:type schema:Person
73 Nc3da072fefba477e913ef6fd88755411 rdf:first sg:person.01203214551.06
74 rdf:rest N9c5319fabb724842a3493c710bab5764
75 Ne0e8b8a4399f43529635c5642bd95b66 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 Nf4da353c265749948e7e75a17af214b9 rdf:first Na250bafef9d346cdac395c2146293e0b
78 rdf:rest rdf:nil
79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
80 schema:name Information and Computing Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
83 schema:name Computation Theory and Mathematics
84 rdf:type schema:DefinedTerm
85 sg:person.01203214551.06 schema:affiliation grid-institutes:grid.37589.30
86 schema:familyName Ho
87 schema:givenName Chin-Wen
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01203214551.06
89 rdf:type schema:Person
90 sg:person.01312526135.27 schema:affiliation grid-institutes:grid.38348.34
91 schema:familyName Tang
92 schema:givenName Chuan Yi
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
94 rdf:type schema:Person
95 sg:person.013531324035.31 schema:affiliation grid-institutes:grid.38348.34
96 schema:familyName Peng
97 schema:givenName Sheng-Lung
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31
99 rdf:type schema:Person
100 sg:person.015756766665.55 schema:affiliation grid-institutes:grid.28665.3f
101 schema:familyName Hsu
102 schema:givenName Tsan-sheng
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015756766665.55
104 rdf:type schema:Person
105 sg:person.07473764745.12 schema:affiliation grid-institutes:grid.28665.3f
106 schema:familyName Ko
107 schema:givenName Ming-Tat
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07473764745.12
109 rdf:type schema:Person
110 grid-institutes:grid.28665.3f schema:alternateName Academia Sinica, Taiwan
111 schema:name Academia Sinica, Taiwan
112 rdf:type schema:Organization
113 grid-institutes:grid.37589.30 schema:alternateName National Central University, Taiwan
114 schema:name National Central University, Taiwan
115 rdf:type schema:Organization
116 grid-institutes:grid.38348.34 schema:alternateName National Tsing Hua University, Taiwan
117 schema:name National Tsing Hua University, Taiwan
118 rdf:type schema:Organization
 




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


...