Constructing Light Spanning Trees with Small Routing Cost View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-04-12

AUTHORS

Bang Ye Wu , Kun-Mao Chao , Chuan Yi Tang

ABSTRACT

Let G = (V, E, w) be an undirected graph with nonnegative edge weight. For any spanning tree T of G, the weight of T is the total weight of its tree edges and the routing cost of T is ∑u, v∈VdT(u, v), where dT(u, v) is the distance between u and v on T. In this paper, we present an algorithm providing a trade off among tree weight, routing cost and time complexity. For any real number α > 1 and an integer 1 < k < 6α - 3, in O(nk+1+n3) time, the algorithm finds a spanning tree whose routing cost is at most (1 + 2/(k + 1)) α times the one of the minimum routing cost tree, and the tree weight is at most (f(k) + 2/(α - 1)) times the one of the minimum spanning tree, where f(k) = 1 if k = 1 and f(k) = 2 if k > 1. More... »

PAGES

334-344

References to SciGraph publications

  • 1993-01. On sparse spanners of weighted graphs in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1995-10. Balancing minimum spanning trees and shortest-path trees in ALGORITHMICA
  • Book

    TITLE

    STACS 99

    ISBN

    978-3-540-65691-3
    978-3-540-49116-3

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-49116-3_31

    DOI

    http://dx.doi.org/10.1007/3-540-49116-3_31

    DIMENSIONS

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


    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": [
                "Dept. of Computer Science, National Tsing Hua University, Hsinchu, 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"
          }, 
          {
            "affiliation": {
              "alternateName": "Providence University", 
              "id": "https://www.grid.ac/institutes/grid.412550.7", 
              "name": [
                "Dept. of Computer Science and Information Management, Providence University, Shalu, Taiwan, R.O.C"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chao", 
            "givenName": "Kun-Mao", 
            "id": "sg:person.01063515113.26", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01063515113.26"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Tsing Hua University", 
              "id": "https://www.grid.ac/institutes/grid.38348.34", 
              "name": [
                "Dept. of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C."
              ], 
              "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"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/28869.28874", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002799108"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.3230080402", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007364680"
            ], 
            "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": "sg:pub.10.1007/bf01294129", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049818437", 
              "https://doi.org/10.1007/bf01294129"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01294129", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049818437", 
              "https://doi.org/10.1007/bf01294129"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0203015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841229"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0601008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062848632"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002-04-12", 
        "datePublishedReg": "2002-04-12", 
        "description": "Let G = (V, E, w) be an undirected graph with nonnegative edge weight. For any spanning tree T of G, the weight of T is the total weight of its tree edges and the routing cost of T is \u2211u, v\u2208VdT(u, v), where dT(u, v) is the distance between u and v on T. In this paper, we present an algorithm providing a trade off among tree weight, routing cost and time complexity. For any real number \u03b1 > 1 and an integer 1 < k < 6\u03b1 - 3, in O(nk+1+n3) time, the algorithm finds a spanning tree whose routing cost is at most (1 + 2/(k + 1)) \u03b1 times the one of the minimum routing cost tree, and the tree weight is at most (f(k) + 2/(\u03b1 - 1)) times the one of the minimum spanning tree, where f(k) = 1 if k = 1 and f(k) = 2 if k > 1.", 
        "editor": [
          {
            "familyName": "Meinel", 
            "givenName": "Christoph", 
            "type": "Person"
          }, 
          {
            "familyName": "Tison", 
            "givenName": "Sophie", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-49116-3_31", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-65691-3", 
            "978-3-540-49116-3"
          ], 
          "name": "STACS 99", 
          "type": "Book"
        }, 
        "name": "Constructing Light Spanning Trees with Small Routing Cost", 
        "pagination": "334-344", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-49116-3_31"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b07b7f1fdc90c169d277bc6906d3a142c9dfcd48537fcc5f2b6e389e3bb4d355"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1037047769"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-49116-3_31", 
          "https://app.dimensions.ai/details/publication/pub.1037047769"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:23", 
        "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/0000000345_0000000345/records_64082_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-49116-3_31"
      }
    ]
     

    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-49116-3_31'

    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-49116-3_31'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-49116-3_31'

    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-49116-3_31'


     

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

    107 TRIPLES      23 PREDICATES      32 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-49116-3_31 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nea6d01cb92a6460f85fd2a6d2257a697
    4 schema:citation sg:pub.10.1007/bf01294129
    5 sg:pub.10.1007/bf02189308
    6 https://doi.org/10.1002/net.3230080402
    7 https://doi.org/10.1137/0203015
    8 https://doi.org/10.1137/0601008
    9 https://doi.org/10.1145/28869.28874
    10 schema:datePublished 2002-04-12
    11 schema:datePublishedReg 2002-04-12
    12 schema:description Let G = (V, E, w) be an undirected graph with nonnegative edge weight. For any spanning tree T of G, the weight of T is the total weight of its tree edges and the routing cost of T is ∑u, v∈VdT(u, v), where dT(u, v) is the distance between u and v on T. In this paper, we present an algorithm providing a trade off among tree weight, routing cost and time complexity. For any real number α > 1 and an integer 1 < k < 6α - 3, in O(nk+1+n3) time, the algorithm finds a spanning tree whose routing cost is at most (1 + 2/(k + 1)) α times the one of the minimum routing cost tree, and the tree weight is at most (f(k) + 2/(α - 1)) times the one of the minimum spanning tree, where f(k) = 1 if k = 1 and f(k) = 2 if k > 1.
    13 schema:editor Neef3b600e9534e1ab09612a71e6f3ba2
    14 schema:genre chapter
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf Nd23cd2252af64c7790567f1aba0a9106
    18 schema:name Constructing Light Spanning Trees with Small Routing Cost
    19 schema:pagination 334-344
    20 schema:productId N688c50d7a9fa4532a828efaf6d903718
    21 N8c678b470e5246ddb15f3dd7a5fc998c
    22 Nbe7194dcd59445a7ba738b1b45f24ff7
    23 schema:publisher Nbd6afb8bc04c4b5e8b077b1f797e0516
    24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037047769
    25 https://doi.org/10.1007/3-540-49116-3_31
    26 schema:sdDatePublished 2019-04-16T05:23
    27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    28 schema:sdPublisher N3e8bc604678341cfb1cb36f50e3b78e5
    29 schema:url https://link.springer.com/10.1007%2F3-540-49116-3_31
    30 sgo:license sg:explorer/license/
    31 sgo:sdDataset chapters
    32 rdf:type schema:Chapter
    33 N3c28baa4480e40c89506958a283c1e91 rdf:first sg:person.01312526135.27
    34 rdf:rest rdf:nil
    35 N3e8bc604678341cfb1cb36f50e3b78e5 schema:name Springer Nature - SN SciGraph project
    36 rdf:type schema:Organization
    37 N560539483d044955a18ec664b6444a5a schema:familyName Meinel
    38 schema:givenName Christoph
    39 rdf:type schema:Person
    40 N590ec64ea2854c5c83df1880f5dee070 schema:familyName Tison
    41 schema:givenName Sophie
    42 rdf:type schema:Person
    43 N688c50d7a9fa4532a828efaf6d903718 schema:name readcube_id
    44 schema:value b07b7f1fdc90c169d277bc6906d3a142c9dfcd48537fcc5f2b6e389e3bb4d355
    45 rdf:type schema:PropertyValue
    46 N8c678b470e5246ddb15f3dd7a5fc998c schema:name doi
    47 schema:value 10.1007/3-540-49116-3_31
    48 rdf:type schema:PropertyValue
    49 N91ae466b72df4610a56dba6f7f608650 rdf:first sg:person.01063515113.26
    50 rdf:rest N3c28baa4480e40c89506958a283c1e91
    51 Nbd6afb8bc04c4b5e8b077b1f797e0516 schema:location Berlin, Heidelberg
    52 schema:name Springer Berlin Heidelberg
    53 rdf:type schema:Organisation
    54 Nbe7194dcd59445a7ba738b1b45f24ff7 schema:name dimensions_id
    55 schema:value pub.1037047769
    56 rdf:type schema:PropertyValue
    57 Nd23cd2252af64c7790567f1aba0a9106 schema:isbn 978-3-540-49116-3
    58 978-3-540-65691-3
    59 schema:name STACS 99
    60 rdf:type schema:Book
    61 Ne0cabd7a3da74a2b9ebaf9eb0f3dbc1a rdf:first N590ec64ea2854c5c83df1880f5dee070
    62 rdf:rest rdf:nil
    63 Nea6d01cb92a6460f85fd2a6d2257a697 rdf:first sg:person.013045767237.23
    64 rdf:rest N91ae466b72df4610a56dba6f7f608650
    65 Neef3b600e9534e1ab09612a71e6f3ba2 rdf:first N560539483d044955a18ec664b6444a5a
    66 rdf:rest Ne0cabd7a3da74a2b9ebaf9eb0f3dbc1a
    67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Information and Computing Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Computation Theory and Mathematics
    72 rdf:type schema:DefinedTerm
    73 sg:person.01063515113.26 schema:affiliation https://www.grid.ac/institutes/grid.412550.7
    74 schema:familyName Chao
    75 schema:givenName Kun-Mao
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01063515113.26
    77 rdf:type schema:Person
    78 sg:person.013045767237.23 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
    79 schema:familyName Wu
    80 schema:givenName Bang Ye
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
    82 rdf:type schema:Person
    83 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
    84 schema:familyName Tang
    85 schema:givenName Chuan Yi
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
    87 rdf:type schema:Person
    88 sg:pub.10.1007/bf01294129 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049818437
    89 https://doi.org/10.1007/bf01294129
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/bf02189308 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012559153
    92 https://doi.org/10.1007/bf02189308
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1002/net.3230080402 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007364680
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1137/0203015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841229
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1137/0601008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848632
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1145/28869.28874 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002799108
    101 rdf:type schema:CreativeWork
    102 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
    103 schema:name Dept. of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C.
    104 rdf:type schema:Organization
    105 https://www.grid.ac/institutes/grid.412550.7 schema:alternateName Providence University
    106 schema:name Dept. of Computer Science and Information Management, Providence University, Shalu, Taiwan, R.O.C
    107 rdf:type schema:Organization
     




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


    ...