Finding Centers and Medians of a Tree by Distance Queries View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2014

AUTHORS

Bang Ye Wu

ABSTRACT

We investigate the problem of finding centers and medians of a tree on the distance oracle model. In this model, the tree is not given as the input and the cost is counted by the number of performed queries for distances between leaves. We show that 2n − 3 queries are necessary and sufficient for finding the diameter, the radius, and the centers, where n is the number of leaves. For the median problem, we propose an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$n\lg n$\end{document}-queries deterministic algorithm and a randomized algorithm with less than 6n expected queries. More... »

PAGES

352-363

Book

TITLE

Fun with Algorithms

ISBN

978-3-319-07889-2
978-3-319-07890-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-07890-8_30

DOI

http://dx.doi.org/10.1007/978-3-319-07890-8_30

DIMENSIONS

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


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/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0607", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Plant Biology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Bang Ye", 
        "id": "sg:person.013045767237.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "We investigate the problem of finding centers and medians of a tree on the distance oracle model. In this model, the tree is not given as the input and the cost is counted by the number of performed queries for distances between leaves. We show that 2n\u2009\u2212\u20093 queries are necessary and sufficient for finding the diameter, the radius, and the centers, where n is the number of leaves. For the median problem, we propose an \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$n\\lg n$\\end{document}-queries deterministic algorithm and a randomized algorithm with less than 6n expected queries.", 
    "editor": [
      {
        "familyName": "Ferro", 
        "givenName": "Alfredo", 
        "type": "Person"
      }, 
      {
        "familyName": "Luccio", 
        "givenName": "Fabrizio", 
        "type": "Person"
      }, 
      {
        "familyName": "Widmayer", 
        "givenName": "Peter", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-07890-8_30", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-07889-2", 
        "978-3-319-07890-8"
      ], 
      "name": "Fun with Algorithms", 
      "type": "Book"
    }, 
    "keywords": [
      "median", 
      "center", 
      "findings centre", 
      "number", 
      "model", 
      "diameter", 
      "problem", 
      "cost", 
      "input", 
      "trees", 
      "distance", 
      "leaves", 
      "oracle model", 
      "queries", 
      "radius", 
      "number of leaves", 
      "median problem", 
      "deterministic algorithm", 
      "algorithm", 
      "randomized algorithm", 
      "distance queries", 
      "distance oracle model"
    ], 
    "name": "Finding Centers and Medians of a Tree by Distance Queries", 
    "pagination": "352-363", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048221144"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-07890-8_30"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-07890-8_30", 
      "https://app.dimensions.ai/details/publication/pub.1048221144"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:13", 
    "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_77.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-07890-8_30"
  }
]
 

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-319-07890-8_30'

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-319-07890-8_30'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-07890-8_30'

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-319-07890-8_30'


 

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

92 TRIPLES      23 PREDICATES      48 URIs      41 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-07890-8_30 schema:about anzsrc-for:06
2 anzsrc-for:0607
3 schema:author Nacdb1ef32e2d4097b64d80cfbd84e3ae
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema:description We investigate the problem of finding centers and medians of a tree on the distance oracle model. In this model, the tree is not given as the input and the cost is counted by the number of performed queries for distances between leaves. We show that 2n − 3 queries are necessary and sufficient for finding the diameter, the radius, and the centers, where n is the number of leaves. For the median problem, we propose an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$n\lg n$\end{document}-queries deterministic algorithm and a randomized algorithm with less than 6n expected queries.
7 schema:editor N4e29b9ad7be145299ef7237662dcfd46
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N771337223fba4795a133013c134e488d
12 schema:keywords algorithm
13 center
14 cost
15 deterministic algorithm
16 diameter
17 distance
18 distance oracle model
19 distance queries
20 findings centre
21 input
22 leaves
23 median
24 median problem
25 model
26 number
27 number of leaves
28 oracle model
29 problem
30 queries
31 radius
32 randomized algorithm
33 trees
34 schema:name Finding Centers and Medians of a Tree by Distance Queries
35 schema:pagination 352-363
36 schema:productId N25974bc0363a43e2953ebc6c88101415
37 Na514ce938d6442499aa35319b278b05c
38 schema:publisher N9944e3c420894b1dac37bbb7783b86ec
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048221144
40 https://doi.org/10.1007/978-3-319-07890-8_30
41 schema:sdDatePublished 2021-12-01T20:13
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher Ne91d7b4e2ccc48d4a9962298712a8ec3
44 schema:url https://doi.org/10.1007/978-3-319-07890-8_30
45 sgo:license sg:explorer/license/
46 sgo:sdDataset chapters
47 rdf:type schema:Chapter
48 N0b47c1aafa2c46b7bb6092d2df0180aa rdf:first Nebb7eb3847604d1fab83c2b1ed721757
49 rdf:rest rdf:nil
50 N25974bc0363a43e2953ebc6c88101415 schema:name doi
51 schema:value 10.1007/978-3-319-07890-8_30
52 rdf:type schema:PropertyValue
53 N4e29b9ad7be145299ef7237662dcfd46 rdf:first Nd230328831c7429f8a0b91ed0fb0a1b3
54 rdf:rest N4fd5d16b75e34dca926d6e3b8ca4f0c3
55 N4fd5d16b75e34dca926d6e3b8ca4f0c3 rdf:first Neb60e5c7934f46ff9ba57aacf6941a13
56 rdf:rest N0b47c1aafa2c46b7bb6092d2df0180aa
57 N771337223fba4795a133013c134e488d schema:isbn 978-3-319-07889-2
58 978-3-319-07890-8
59 schema:name Fun with Algorithms
60 rdf:type schema:Book
61 N9944e3c420894b1dac37bbb7783b86ec schema:name Springer Nature
62 rdf:type schema:Organisation
63 Na514ce938d6442499aa35319b278b05c schema:name dimensions_id
64 schema:value pub.1048221144
65 rdf:type schema:PropertyValue
66 Nacdb1ef32e2d4097b64d80cfbd84e3ae rdf:first sg:person.013045767237.23
67 rdf:rest rdf:nil
68 Nd230328831c7429f8a0b91ed0fb0a1b3 schema:familyName Ferro
69 schema:givenName Alfredo
70 rdf:type schema:Person
71 Ne91d7b4e2ccc48d4a9962298712a8ec3 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 Neb60e5c7934f46ff9ba57aacf6941a13 schema:familyName Luccio
74 schema:givenName Fabrizio
75 rdf:type schema:Person
76 Nebb7eb3847604d1fab83c2b1ed721757 schema:familyName Widmayer
77 schema:givenName Peter
78 rdf:type schema:Person
79 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
80 schema:name Biological Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
83 schema:name Plant Biology
84 rdf:type schema:DefinedTerm
85 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
86 schema:familyName Wu
87 schema:givenName Bang Ye
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
89 rdf:type schema:Person
90 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
91 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
92 rdf:type schema:Organization
 




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


...