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 N6610d17d2e0d471cace299ab3f8bb903
    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 N884f149bcc2e48b9a427b8b532ae7308
    14 schema:genre chapter
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf Nf1cf8d4e86b94fa7b4658ea9fd22ee91
    18 schema:name Constructing Light Spanning Trees with Small Routing Cost
    19 schema:pagination 334-344
    20 schema:productId N39cf6cfff023468b89312aa5f1698cf3
    21 N59afe9a848b24a61a20497ba49d893e3
    22 N959063f44f2b409f8eb44358db7c2fee
    23 schema:publisher N5a7d7a8284c64ed08b513c710a2697f6
    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 N194e1d39dba4441d931ef40fecae43e1
    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 N194e1d39dba4441d931ef40fecae43e1 schema:name Springer Nature - SN SciGraph project
    34 rdf:type schema:Organization
    35 N1e96f1145c1b4921b555bf410a0ecaff rdf:first Nc7ca278e44fa4ee499d7cfe99ecbb24e
    36 rdf:rest rdf:nil
    37 N39cf6cfff023468b89312aa5f1698cf3 schema:name doi
    38 schema:value 10.1007/3-540-49116-3_31
    39 rdf:type schema:PropertyValue
    40 N4aaee0d14bc94e01844289597f19f421 rdf:first sg:person.01312526135.27
    41 rdf:rest rdf:nil
    42 N59afe9a848b24a61a20497ba49d893e3 schema:name dimensions_id
    43 schema:value pub.1037047769
    44 rdf:type schema:PropertyValue
    45 N5a7d7a8284c64ed08b513c710a2697f6 schema:location Berlin, Heidelberg
    46 schema:name Springer Berlin Heidelberg
    47 rdf:type schema:Organisation
    48 N6610d17d2e0d471cace299ab3f8bb903 rdf:first sg:person.013045767237.23
    49 rdf:rest N7e50c0b5fd8c4f9b8020be94ea037090
    50 N7e50c0b5fd8c4f9b8020be94ea037090 rdf:first sg:person.01063515113.26
    51 rdf:rest N4aaee0d14bc94e01844289597f19f421
    52 N884f149bcc2e48b9a427b8b532ae7308 rdf:first Ne8fd3469a2c14b9d80056ca59f7f18ed
    53 rdf:rest N1e96f1145c1b4921b555bf410a0ecaff
    54 N959063f44f2b409f8eb44358db7c2fee schema:name readcube_id
    55 schema:value b07b7f1fdc90c169d277bc6906d3a142c9dfcd48537fcc5f2b6e389e3bb4d355
    56 rdf:type schema:PropertyValue
    57 Nc7ca278e44fa4ee499d7cfe99ecbb24e schema:familyName Tison
    58 schema:givenName Sophie
    59 rdf:type schema:Person
    60 Ne8fd3469a2c14b9d80056ca59f7f18ed schema:familyName Meinel
    61 schema:givenName Christoph
    62 rdf:type schema:Person
    63 Nf1cf8d4e86b94fa7b4658ea9fd22ee91 schema:isbn 978-3-540-49116-3
    64 978-3-540-65691-3
    65 schema:name STACS 99
    66 rdf:type schema:Book
    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)


    ...