Balancing minimum spanning trees and shortest-path trees View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1995-10

AUTHORS

S. Khuller, B. Raghavachari, N. Young

ABSTRACT

We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and aγ>0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+√2γ times the shortest-path distance, and yet the total weight of the tree is at most 1+√2/γ times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex. More... »

PAGES

305-321

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0607", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Plant Biology", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Maryland, College Park", 
          "id": "https://www.grid.ac/institutes/grid.164295.d", 
          "name": [
            "Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742, College Park, MD, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Khuller", 
        "givenName": "S.", 
        "id": "sg:person.0702635444.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0702635444.36"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "The University of Texas at Dallas", 
          "id": "https://www.grid.ac/institutes/grid.267323.1", 
          "name": [
            "Department of Computer Science, University of Texas at Dallas, Box 830688, 75083-0688, Richardson, TX, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raghavachari", 
        "givenName": "B.", 
        "id": "sg:person.016267033065.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016267033065.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Princeton University", 
          "id": "https://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Department of Computer Science, Princeton University, 08544, Princeton, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Young", 
        "givenName": "N.", 
        "id": "sg:person.0716275540.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0716275540.43"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/28869.28874", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002799108"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579168", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009027313", 
          "https://doi.org/10.1007/bf02579168"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579168", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009027313", 
          "https://doi.org/10.1007/bf02579168"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(89)90044-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010096427"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02189308", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012559153", 
          "https://doi.org/10.1007/bf02189308"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02189308", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012559153", 
          "https://doi.org/10.1007/bf02189308"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9939-1956-0078686-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018477579"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1021021236", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-1098-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021021236", 
          "https://doi.org/10.1007/978-1-4612-1098-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-1098-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021021236", 
          "https://doi.org/10.1007/978-1-4612-1098-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/j.1538-7305.1957.tb01515.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025892743"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02574695", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040312871", 
          "https://doi.org/10.1007/bf02574695"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02574695", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040312871", 
          "https://doi.org/10.1007/bf02574695"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01386390", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041716633", 
          "https://doi.org/10.1007/bf01386390"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01758846", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044918058", 
          "https://doi.org/10.1007/bf01758846"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01758846", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044918058", 
          "https://doi.org/10.1007/bf01758846"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/142675.142717", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045652304"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/41840.41847", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046458145"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tcom.1983.1095818", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061553654"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/iscas.1992.230514", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086339595"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1995-10", 
    "datePublishedReg": "1995-10-01", 
    "description": "We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and a\u03b3>0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+\u221a2\u03b3 times the shortest-path distance, and yet the total weight of the tree is at most 1+\u221a2/\u03b3 times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01294129", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "14"
      }
    ], 
    "name": "Balancing minimum spanning trees and shortest-path trees", 
    "pagination": "305-321", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ed51d223852da2d0f684042950825a60f5bcc61ed5dd110c40a5ce7805690197"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01294129"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049818437"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01294129", 
      "https://app.dimensions.ai/details/publication/pub.1049818437"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13: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/0000000370_0000000370/records_46757_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01294129"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

131 TRIPLES      21 PREDICATES      42 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01294129 schema:about anzsrc-for:06
2 anzsrc-for:0607
3 schema:author N5b66e35378554ee4bcfe8e7f4a3c48b6
4 schema:citation sg:pub.10.1007/978-1-4612-1098-6
5 sg:pub.10.1007/bf01386390
6 sg:pub.10.1007/bf01758846
7 sg:pub.10.1007/bf02189308
8 sg:pub.10.1007/bf02574695
9 sg:pub.10.1007/bf02579168
10 https://app.dimensions.ai/details/publication/pub.1021021236
11 https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
12 https://doi.org/10.1016/0022-0000(89)90044-5
13 https://doi.org/10.1090/s0002-9939-1956-0078686-7
14 https://doi.org/10.1109/iscas.1992.230514
15 https://doi.org/10.1109/tcom.1983.1095818
16 https://doi.org/10.1145/142675.142717
17 https://doi.org/10.1145/28869.28874
18 https://doi.org/10.1145/41840.41847
19 schema:datePublished 1995-10
20 schema:datePublishedReg 1995-10-01
21 schema:description We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and aγ>0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+√2γ times the shortest-path distance, and yet the total weight of the tree is at most 1+√2/γ times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex.
22 schema:genre research_article
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N66f33485ebae494490902eb6c40b994e
26 Neea18b3a9e874af39a9c711c1ed9f8f4
27 sg:journal.1047644
28 schema:name Balancing minimum spanning trees and shortest-path trees
29 schema:pagination 305-321
30 schema:productId N173a5c11527c4277bc0d07f750c6dd69
31 N701150b074294b0993eb927fe33f85d3
32 Nf337ad8183c140359e4dce3a832e42af
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049818437
34 https://doi.org/10.1007/bf01294129
35 schema:sdDatePublished 2019-04-11T13:31
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher N3f1fc9f0383f4eb68ef664bd1fb81a27
38 schema:url http://link.springer.com/10.1007/BF01294129
39 sgo:license sg:explorer/license/
40 sgo:sdDataset articles
41 rdf:type schema:ScholarlyArticle
42 N173a5c11527c4277bc0d07f750c6dd69 schema:name doi
43 schema:value 10.1007/bf01294129
44 rdf:type schema:PropertyValue
45 N3f1fc9f0383f4eb68ef664bd1fb81a27 schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 N412381c1a8804091b6cea2b5a7dfbd3d rdf:first sg:person.016267033065.01
48 rdf:rest N864dbb4a6c894e5cb1ffaec34a5b0e39
49 N5b66e35378554ee4bcfe8e7f4a3c48b6 rdf:first sg:person.0702635444.36
50 rdf:rest N412381c1a8804091b6cea2b5a7dfbd3d
51 N66f33485ebae494490902eb6c40b994e schema:volumeNumber 14
52 rdf:type schema:PublicationVolume
53 N701150b074294b0993eb927fe33f85d3 schema:name dimensions_id
54 schema:value pub.1049818437
55 rdf:type schema:PropertyValue
56 N864dbb4a6c894e5cb1ffaec34a5b0e39 rdf:first sg:person.0716275540.43
57 rdf:rest rdf:nil
58 Neea18b3a9e874af39a9c711c1ed9f8f4 schema:issueNumber 4
59 rdf:type schema:PublicationIssue
60 Nf337ad8183c140359e4dce3a832e42af schema:name readcube_id
61 schema:value ed51d223852da2d0f684042950825a60f5bcc61ed5dd110c40a5ce7805690197
62 rdf:type schema:PropertyValue
63 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
64 schema:name Biological Sciences
65 rdf:type schema:DefinedTerm
66 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
67 schema:name Plant Biology
68 rdf:type schema:DefinedTerm
69 sg:journal.1047644 schema:issn 0178-4617
70 1432-0541
71 schema:name Algorithmica
72 rdf:type schema:Periodical
73 sg:person.016267033065.01 schema:affiliation https://www.grid.ac/institutes/grid.267323.1
74 schema:familyName Raghavachari
75 schema:givenName B.
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016267033065.01
77 rdf:type schema:Person
78 sg:person.0702635444.36 schema:affiliation https://www.grid.ac/institutes/grid.164295.d
79 schema:familyName Khuller
80 schema:givenName S.
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0702635444.36
82 rdf:type schema:Person
83 sg:person.0716275540.43 schema:affiliation https://www.grid.ac/institutes/grid.16750.35
84 schema:familyName Young
85 schema:givenName N.
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0716275540.43
87 rdf:type schema:Person
88 sg:pub.10.1007/978-1-4612-1098-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021021236
89 https://doi.org/10.1007/978-1-4612-1098-6
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/bf01386390 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041716633
92 https://doi.org/10.1007/bf01386390
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/bf01758846 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044918058
95 https://doi.org/10.1007/bf01758846
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/bf02189308 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012559153
98 https://doi.org/10.1007/bf02189308
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/bf02574695 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040312871
101 https://doi.org/10.1007/bf02574695
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/bf02579168 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009027313
104 https://doi.org/10.1007/bf02579168
105 rdf:type schema:CreativeWork
106 https://app.dimensions.ai/details/publication/pub.1021021236 schema:CreativeWork
107 https://doi.org/10.1002/j.1538-7305.1957.tb01515.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1025892743
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/0022-0000(89)90044-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010096427
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1090/s0002-9939-1956-0078686-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018477579
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1109/iscas.1992.230514 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086339595
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1109/tcom.1983.1095818 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061553654
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1145/142675.142717 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045652304
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1145/28869.28874 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002799108
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1145/41840.41847 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046458145
122 rdf:type schema:CreativeWork
123 https://www.grid.ac/institutes/grid.164295.d schema:alternateName University of Maryland, College Park
124 schema:name Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742, College Park, MD, USA
125 rdf:type schema:Organization
126 https://www.grid.ac/institutes/grid.16750.35 schema:alternateName Princeton University
127 schema:name Department of Computer Science, Princeton University, 08544, Princeton, NJ, USA
128 rdf:type schema:Organization
129 https://www.grid.ac/institutes/grid.267323.1 schema:alternateName The University of Texas at Dallas
130 schema:name Department of Computer Science, University of Texas at Dallas, Box 830688, 75083-0688, Richardson, TX, USA
131 rdf:type schema:Organization
 




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


...