The slab dividing approach to solve the EuclideanP-Center problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-01

AUTHORS

R. Z. Hwang, R. C. T. Lee, R. C. Chang

ABSTRACT

Givenn demand points on the plane, the EuclideanP-Center problem is to findP supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, isO(n2p−1· logn). In this paper, we present an algorithm with time complexityO(n0(√P)). More... »

PAGES

1-22

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hwang", 
        "givenName": "R. Z.", 
        "id": "sg:person.014072526441.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014072526441.41"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Academia Sinica, Taipei, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China", 
            "Academia Sinica, Taipei, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lee", 
        "givenName": "R. C. T.", 
        "id": "sg:person.07540250215.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, National Chiao Tung University, Hsinchu, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.260539.b", 
          "name": [
            "Academia Sinica, Taipei, Taiwan, Republic of China", 
            "Institute of Computer Science, National Chiao Tung University, Hsinchu, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "R. C.", 
        "id": "sg:person.012355347703.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012355347703.02"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1057/jors.1984.150", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029954112", 
          "https://doi.org/10.1057/jors.1984.150"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-61568-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049996833", 
          "https://doi.org/10.1007/978-3-642-61568-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-69897-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017401984", 
          "https://doi.org/10.1007/978-3-642-69897-2"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1993-01", 
    "datePublishedReg": "1993-01-01", 
    "description": "Givenn demand points on the plane, the EuclideanP-Center problem is to findP supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, isO(n2p\u22121\u00b7 logn). In this paper, we present an algorithm with time complexityO(n0(\u221aP)).", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01185335", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "9"
      }
    ], 
    "keywords": [
      "demand points", 
      "supply points", 
      "efficient algorithm", 
      "time complexity", 
      "problem", 
      "algorithm", 
      "point", 
      "complexity", 
      "approach", 
      "plane", 
      "distance", 
      "time", 
      "long distances", 
      "slab", 
      "paper", 
      "Givenn demand points", 
      "EuclideanP-Center problem", 
      "findP supply points", 
      "closest supply point"
    ], 
    "name": "The slab dividing approach to solve the EuclideanP-Center problem", 
    "pagination": "1-22", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046727991"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01185335"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01185335", 
      "https://app.dimensions.ai/details/publication/pub.1046727991"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-12-01T19:07", 
    "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/article/article_228.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01185335"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

111 TRIPLES      22 PREDICATES      48 URIs      37 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01185335 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N395a296e33084d61a70c6180515665b9
4 schema:citation sg:pub.10.1007/978-3-642-61568-9
5 sg:pub.10.1007/978-3-642-69897-2
6 sg:pub.10.1057/jors.1984.150
7 schema:datePublished 1993-01
8 schema:datePublishedReg 1993-01-01
9 schema:description Givenn demand points on the plane, the EuclideanP-Center problem is to findP supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, isO(n2p−1· logn). In this paper, we present an algorithm with time complexityO(n0(√P)).
10 schema:genre article
11 schema:inLanguage en
12 schema:isAccessibleForFree false
13 schema:isPartOf Nd3cacb964d5b46ad8930ab9dd4e2dbcf
14 Ndafae4a4674348aa88cbcf6ddeff0ec0
15 sg:journal.1047644
16 schema:keywords EuclideanP-Center problem
17 Givenn demand points
18 algorithm
19 approach
20 closest supply point
21 complexity
22 demand points
23 distance
24 efficient algorithm
25 findP supply points
26 long distances
27 paper
28 plane
29 point
30 problem
31 slab
32 supply points
33 time
34 time complexity
35 schema:name The slab dividing approach to solve the EuclideanP-Center problem
36 schema:pagination 1-22
37 schema:productId Na9857b7cc45843df8d3d6788dc8b207a
38 Naaedaab7fa9c4990a9a7a1fb3bbcce06
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046727991
40 https://doi.org/10.1007/bf01185335
41 schema:sdDatePublished 2021-12-01T19:07
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N36160c4c11f746558224ce92520ea183
44 schema:url https://doi.org/10.1007/bf01185335
45 sgo:license sg:explorer/license/
46 sgo:sdDataset articles
47 rdf:type schema:ScholarlyArticle
48 N36160c4c11f746558224ce92520ea183 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N395a296e33084d61a70c6180515665b9 rdf:first sg:person.014072526441.41
51 rdf:rest Nc657359e97d94818804689b5130b2b87
52 N4acee66267d847cc919b4cbc4cc73fbc rdf:first sg:person.012355347703.02
53 rdf:rest rdf:nil
54 Na9857b7cc45843df8d3d6788dc8b207a schema:name dimensions_id
55 schema:value pub.1046727991
56 rdf:type schema:PropertyValue
57 Naaedaab7fa9c4990a9a7a1fb3bbcce06 schema:name doi
58 schema:value 10.1007/bf01185335
59 rdf:type schema:PropertyValue
60 Nc657359e97d94818804689b5130b2b87 rdf:first sg:person.07540250215.50
61 rdf:rest N4acee66267d847cc919b4cbc4cc73fbc
62 Nd3cacb964d5b46ad8930ab9dd4e2dbcf schema:volumeNumber 9
63 rdf:type schema:PublicationVolume
64 Ndafae4a4674348aa88cbcf6ddeff0ec0 schema:issueNumber 1
65 rdf:type schema:PublicationIssue
66 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
67 schema:name Mathematical Sciences
68 rdf:type schema:DefinedTerm
69 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
70 schema:name Numerical and Computational Mathematics
71 rdf:type schema:DefinedTerm
72 sg:journal.1047644 schema:issn 0178-4617
73 1432-0541
74 schema:name Algorithmica
75 schema:publisher Springer Nature
76 rdf:type schema:Periodical
77 sg:person.012355347703.02 schema:affiliation grid-institutes:grid.260539.b
78 schema:familyName Chang
79 schema:givenName R. C.
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012355347703.02
81 rdf:type schema:Person
82 sg:person.014072526441.41 schema:affiliation grid-institutes:grid.38348.34
83 schema:familyName Hwang
84 schema:givenName R. Z.
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014072526441.41
86 rdf:type schema:Person
87 sg:person.07540250215.50 schema:affiliation grid-institutes:grid.28665.3f
88 schema:familyName Lee
89 schema:givenName R. C. T.
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50
91 rdf:type schema:Person
92 sg:pub.10.1007/978-3-642-61568-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049996833
93 https://doi.org/10.1007/978-3-642-61568-9
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/978-3-642-69897-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017401984
96 https://doi.org/10.1007/978-3-642-69897-2
97 rdf:type schema:CreativeWork
98 sg:pub.10.1057/jors.1984.150 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029954112
99 https://doi.org/10.1057/jors.1984.150
100 rdf:type schema:CreativeWork
101 grid-institutes:grid.260539.b schema:alternateName Institute of Computer Science, National Chiao Tung University, Hsinchu, Taiwan, Republic of China
102 schema:name Academia Sinica, Taipei, Taiwan, Republic of China
103 Institute of Computer Science, National Chiao Tung University, Hsinchu, Taiwan, Republic of China
104 rdf:type schema:Organization
105 grid-institutes:grid.28665.3f schema:alternateName Academia Sinica, Taipei, Taiwan, Republic of China
106 schema:name Academia Sinica, Taipei, Taiwan, Republic of China
107 Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China
108 rdf:type schema:Organization
109 grid-institutes:grid.38348.34 schema:alternateName Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China
110 schema:name Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China
111 rdf:type schema:Organization
 




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


...