Computation of Constrained Spanning Trees: A Unified Approach View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Narsingh Deo , Nishit Kumar

ABSTRACT

Computing spanning trees with specific properties and constraints lies at the heart of many real-life network optimization problems. Here, a compilation of 29 constrained spanning tree problems is presented. Since most of these problems are NP-complete, good approximate heuristics are needed to solve them on parallel machines. We develop two generic methods for handling large graphs on massively-parallel SIMD machines. The first method is for problems in which the goal is to find a spanning tree which satisfies a specified constraint while minimizing its total weight., First, a minimum spanning tree (MST) of the given weighted graph is computed without considering the specified constraint. Then, the constraint is used to increase the weights of selected edges (in this tree) in order that when the next MST is constructed (in the graph with modified edge weights) it has fewer violations of the constraint. Next, an MST of the graph with altered weights is computed. This iterative procedure of increasing the edge weights followed by the MST computation is repeated until a spanning tree without constraint violations is obtained. The second method, on the other hand, constructs a spanning tree once and for all — employing problem-specific heuristics in every step of the tree-construction. As case studies, we consider two sample problems (Degree-Constrained MST and Minimun-Length Fundamental-Cycle-Set) — one for each of the two methods. Our extensive empirical study on well-known benchmark problems as well as on randomly-generated graphs shows that the quality of solutions for both the problems is promising and the execution-times, reasonable for graphs with thousands of nodes and several million edges. Finally, to demonstrate the generality of our approach, we outline how to apply these two methods to three additional problems from the list, namely — Capacitated MST, Maximum-Leaf Spanning Tree,and Optimum-Communication Spanning Tree. For the Optimum-Communication Spanning Tree, a hybrid of the two methods is employed. More... »

PAGES

196-220

References to SciGraph publications

Book

TITLE

Network Optimization

ISBN

978-3-540-62541-4
978-3-642-59179-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-59179-2_10

DOI

http://dx.doi.org/10.1007/978-3-642-59179-2_10

DIMENSIONS

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


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": "University of Central Florida", 
          "id": "https://www.grid.ac/institutes/grid.170430.1", 
          "name": [
            "University of Central Florida, 32816-2362, Orlando, FL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Deo", 
        "givenName": "Narsingh", 
        "id": "sg:person.010274011142.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Central Florida", 
          "id": "https://www.grid.ac/institutes/grid.170430.1", 
          "name": [
            "University of Central Florida, 32816-2362, Orlando, FL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kumar", 
        "givenName": "Nishit", 
        "id": "sg:person.010755210471.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010755210471.30"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02031706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001325951", 
          "https://doi.org/10.1007/bf02031706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02031706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001325951", 
          "https://doi.org/10.1007/bf02031706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322358.322367", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002375000"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230080402", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007364680"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230080306", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007538971"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007977430", 
          "https://doi.org/10.1007/978-1-4684-2001-2_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-8191(05)80155-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011659586"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0196-6774(85)90025-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012376171"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230200302", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013743346"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230080304", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014134583"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0377-2217(80)90164-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016999432"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0377-2217(80)90164-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016999432"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230230603", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022514573"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0038190", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025966794", 
          "https://doi.org/10.1007/bfb0038190"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322307.322309", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026688263"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(83)90014-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026792880"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(83)90014-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026792880"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230120402", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027837039"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/195058.195212", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030898039"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0030880", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031077350", 
          "https://doi.org/10.1007/bfb0030880"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02288325", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035664559", 
          "https://doi.org/10.1007/bf02288325"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02288325", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035664559", 
          "https://doi.org/10.1007/bf02288325"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-8191(93)90089-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035937254"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-8191(93)90089-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035937254"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0028279", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037242577", 
          "https://doi.org/10.1007/bfb0028279"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/103418.103437", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038049103"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01188713", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040062640", 
          "https://doi.org/10.1007/bf01188713"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01188713", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040062640", 
          "https://doi.org/10.1007/bf01188713"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(81)90004-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043047063"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/1520-6750(199204)39:3<399::aid-nav3220390309>3.0.co;2-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043245120"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(94)90139-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043652978"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230230805", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043795778"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0096-3003(94)90126-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043819377"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/168173.168420", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044687664"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1155/1994/20983", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046824898"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230070405", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048482235"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1048681974", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2363-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048681974", 
          "https://doi.org/10.1007/978-1-4757-2363-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2363-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048681974", 
          "https://doi.org/10.1007/978-1-4757-2363-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/355984.355988", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052782062"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0377-2217(92)90317-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053541192"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0377-2217(92)90317-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053541192"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/43.137519", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061172562"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/43.331412", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061173164"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/82.204128", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061237597"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tct.1966.1082617", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061578302"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0134037", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062839697"
        ], 
        "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/0216026", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841972"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0220060", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842320"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/ijoc.1.3.190", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064706391"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/ijoc.3.4.376", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064707391"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.38.1.178", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064730077"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.43.1.130", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064730727"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1984.715935", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086163608"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/asic.1992.270316", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086364481"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/dimacs/015", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1097022677"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "Computing spanning trees with specific properties and constraints lies at the heart of many real-life network optimization problems. Here, a compilation of 29 constrained spanning tree problems is presented. Since most of these problems are NP-complete, good approximate heuristics are needed to solve them on parallel machines. We develop two generic methods for handling large graphs on massively-parallel SIMD machines. The first method is for problems in which the goal is to find a spanning tree which satisfies a specified constraint while minimizing its total weight., First, a minimum spanning tree (MST) of the given weighted graph is computed without considering the specified constraint. Then, the constraint is used to increase the weights of selected edges (in this tree) in order that when the next MST is constructed (in the graph with modified edge weights) it has fewer violations of the constraint. Next, an MST of the graph with altered weights is computed. This iterative procedure of increasing the edge weights followed by the MST computation is repeated until a spanning tree without constraint violations is obtained. The second method, on the other hand, constructs a spanning tree once and for all \u2014 employing problem-specific heuristics in every step of the tree-construction. As case studies, we consider two sample problems (Degree-Constrained MST and Minimun-Length Fundamental-Cycle-Set) \u2014 one for each of the two methods. Our extensive empirical study on well-known benchmark problems as well as on randomly-generated graphs shows that the quality of solutions for both the problems is promising and the execution-times, reasonable for graphs with thousands of nodes and several million edges. Finally, to demonstrate the generality of our approach, we outline how to apply these two methods to three additional problems from the list, namely \u2014 Capacitated MST, Maximum-Leaf Spanning Tree,and Optimum-Communication Spanning Tree. For the Optimum-Communication Spanning Tree, a hybrid of the two methods is employed.", 
    "editor": [
      {
        "familyName": "Pardalos", 
        "givenName": "Panos M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Hearn", 
        "givenName": "Donald W.", 
        "type": "Person"
      }, 
      {
        "familyName": "Hager", 
        "givenName": "William W.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-59179-2_10", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-62541-4", 
        "978-3-642-59179-2"
      ], 
      "name": "Network Optimization", 
      "type": "Book"
    }, 
    "name": "Computation of Constrained Spanning Trees: A Unified Approach", 
    "pagination": "196-220", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003656450"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-59179-2_10"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "116af0d5d50395e7d4d06ce9591d756dceec6869bc6cabb2c8aa8e1315767f83"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-59179-2_10", 
      "https://app.dimensions.ai/details/publication/pub.1003656450"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T09:37", 
    "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/0000000373_0000000373/records_13104_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-59179-2_10"
  }
]
 

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-642-59179-2_10'

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-642-59179-2_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-59179-2_10'

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-642-59179-2_10'


 

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

236 TRIPLES      23 PREDICATES      76 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-59179-2_10 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N4147c8841fbb40c6a729f6c19d18b7fc
4 schema:citation sg:pub.10.1007/978-1-4684-2001-2_9
5 sg:pub.10.1007/978-1-4757-2363-2
6 sg:pub.10.1007/bf01188713
7 sg:pub.10.1007/bf02031706
8 sg:pub.10.1007/bf02288325
9 sg:pub.10.1007/bfb0028279
10 sg:pub.10.1007/bfb0030880
11 sg:pub.10.1007/bfb0038190
12 https://app.dimensions.ai/details/publication/pub.1048681974
13 https://doi.org/10.1002/1520-6750(199204)39:3<399::aid-nav3220390309>3.0.co;2-0
14 https://doi.org/10.1002/net.3230070405
15 https://doi.org/10.1002/net.3230080304
16 https://doi.org/10.1002/net.3230080306
17 https://doi.org/10.1002/net.3230080402
18 https://doi.org/10.1002/net.3230120402
19 https://doi.org/10.1002/net.3230200302
20 https://doi.org/10.1002/net.3230230603
21 https://doi.org/10.1002/net.3230230805
22 https://doi.org/10.1016/0020-0190(94)90139-2
23 https://doi.org/10.1016/0096-3003(94)90126-0
24 https://doi.org/10.1016/0166-218x(81)90004-4
25 https://doi.org/10.1016/0166-218x(83)90014-8
26 https://doi.org/10.1016/0167-8191(93)90089-4
27 https://doi.org/10.1016/0196-6774(85)90025-2
28 https://doi.org/10.1016/0377-2217(80)90164-2
29 https://doi.org/10.1016/0377-2217(92)90317-3
30 https://doi.org/10.1016/s0167-8191(05)80155-3
31 https://doi.org/10.1090/dimacs/015
32 https://doi.org/10.1109/43.137519
33 https://doi.org/10.1109/43.331412
34 https://doi.org/10.1109/82.204128
35 https://doi.org/10.1109/asic.1992.270316
36 https://doi.org/10.1109/sfcs.1984.715935
37 https://doi.org/10.1109/tct.1966.1082617
38 https://doi.org/10.1137/0134037
39 https://doi.org/10.1137/0203015
40 https://doi.org/10.1137/0216026
41 https://doi.org/10.1137/0220060
42 https://doi.org/10.1145/103418.103437
43 https://doi.org/10.1145/168173.168420
44 https://doi.org/10.1145/195058.195212
45 https://doi.org/10.1145/322307.322309
46 https://doi.org/10.1145/322358.322367
47 https://doi.org/10.1145/355984.355988
48 https://doi.org/10.1155/1994/20983
49 https://doi.org/10.1287/ijoc.1.3.190
50 https://doi.org/10.1287/ijoc.3.4.376
51 https://doi.org/10.1287/opre.38.1.178
52 https://doi.org/10.1287/opre.43.1.130
53 schema:datePublished 1997
54 schema:datePublishedReg 1997-01-01
55 schema:description Computing spanning trees with specific properties and constraints lies at the heart of many real-life network optimization problems. Here, a compilation of 29 constrained spanning tree problems is presented. Since most of these problems are NP-complete, good approximate heuristics are needed to solve them on parallel machines. We develop two generic methods for handling large graphs on massively-parallel SIMD machines. The first method is for problems in which the goal is to find a spanning tree which satisfies a specified constraint while minimizing its total weight., First, a minimum spanning tree (MST) of the given weighted graph is computed without considering the specified constraint. Then, the constraint is used to increase the weights of selected edges (in this tree) in order that when the next MST is constructed (in the graph with modified edge weights) it has fewer violations of the constraint. Next, an MST of the graph with altered weights is computed. This iterative procedure of increasing the edge weights followed by the MST computation is repeated until a spanning tree without constraint violations is obtained. The second method, on the other hand, constructs a spanning tree once and for all — employing problem-specific heuristics in every step of the tree-construction. As case studies, we consider two sample problems (Degree-Constrained MST and Minimun-Length Fundamental-Cycle-Set) — one for each of the two methods. Our extensive empirical study on well-known benchmark problems as well as on randomly-generated graphs shows that the quality of solutions for both the problems is promising and the execution-times, reasonable for graphs with thousands of nodes and several million edges. Finally, to demonstrate the generality of our approach, we outline how to apply these two methods to three additional problems from the list, namely — Capacitated MST, Maximum-Leaf Spanning Tree,and Optimum-Communication Spanning Tree. For the Optimum-Communication Spanning Tree, a hybrid of the two methods is employed.
56 schema:editor Ndc843910c8a74c3a8d481e3da8ad128f
57 schema:genre chapter
58 schema:inLanguage en
59 schema:isAccessibleForFree false
60 schema:isPartOf N49da2423044047988a5a3956524130c1
61 schema:name Computation of Constrained Spanning Trees: A Unified Approach
62 schema:pagination 196-220
63 schema:productId N13532790ed394f598ece6f4a7a7f0506
64 N4c4935eaa79349b3833b7b690a7a35f2
65 Na5e15911f1a4444faadd59aafe0f9cea
66 schema:publisher N65482ea85c104671bde9bed2bfd5cdf8
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003656450
68 https://doi.org/10.1007/978-3-642-59179-2_10
69 schema:sdDatePublished 2019-04-16T09:37
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N35ed4199622e4789af2b53989f47ddf4
72 schema:url https://link.springer.com/10.1007%2F978-3-642-59179-2_10
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N13532790ed394f598ece6f4a7a7f0506 schema:name dimensions_id
77 schema:value pub.1003656450
78 rdf:type schema:PropertyValue
79 N19bfdfbb4419419b83ff3790af63fd21 schema:familyName Hager
80 schema:givenName William W.
81 rdf:type schema:Person
82 N26d4a52b0ae040a6b2bdc9a1bd6f3acf schema:familyName Pardalos
83 schema:givenName Panos M.
84 rdf:type schema:Person
85 N35ed4199622e4789af2b53989f47ddf4 schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 N4147c8841fbb40c6a729f6c19d18b7fc rdf:first sg:person.010274011142.47
88 rdf:rest N4524f51a380f481287ad16298a550d26
89 N4524f51a380f481287ad16298a550d26 rdf:first sg:person.010755210471.30
90 rdf:rest rdf:nil
91 N49da2423044047988a5a3956524130c1 schema:isbn 978-3-540-62541-4
92 978-3-642-59179-2
93 schema:name Network Optimization
94 rdf:type schema:Book
95 N4c4935eaa79349b3833b7b690a7a35f2 schema:name readcube_id
96 schema:value 116af0d5d50395e7d4d06ce9591d756dceec6869bc6cabb2c8aa8e1315767f83
97 rdf:type schema:PropertyValue
98 N65482ea85c104671bde9bed2bfd5cdf8 schema:location Berlin, Heidelberg
99 schema:name Springer Berlin Heidelberg
100 rdf:type schema:Organisation
101 Na5e15911f1a4444faadd59aafe0f9cea schema:name doi
102 schema:value 10.1007/978-3-642-59179-2_10
103 rdf:type schema:PropertyValue
104 Nb1590f72731d4b028395921b501f6ece rdf:first Nbf912226220048b6960a054b5c68da79
105 rdf:rest Nce33e1bff0834e9987e77517981a0b97
106 Nbf912226220048b6960a054b5c68da79 schema:familyName Hearn
107 schema:givenName Donald W.
108 rdf:type schema:Person
109 Nce33e1bff0834e9987e77517981a0b97 rdf:first N19bfdfbb4419419b83ff3790af63fd21
110 rdf:rest rdf:nil
111 Ndc843910c8a74c3a8d481e3da8ad128f rdf:first N26d4a52b0ae040a6b2bdc9a1bd6f3acf
112 rdf:rest Nb1590f72731d4b028395921b501f6ece
113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
114 schema:name Information and Computing Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
117 schema:name Computation Theory and Mathematics
118 rdf:type schema:DefinedTerm
119 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
120 schema:familyName Deo
121 schema:givenName Narsingh
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
123 rdf:type schema:Person
124 sg:person.010755210471.30 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
125 schema:familyName Kumar
126 schema:givenName Nishit
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010755210471.30
128 rdf:type schema:Person
129 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
130 https://doi.org/10.1007/978-1-4684-2001-2_9
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/978-1-4757-2363-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048681974
133 https://doi.org/10.1007/978-1-4757-2363-2
134 rdf:type schema:CreativeWork
135 sg:pub.10.1007/bf01188713 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040062640
136 https://doi.org/10.1007/bf01188713
137 rdf:type schema:CreativeWork
138 sg:pub.10.1007/bf02031706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001325951
139 https://doi.org/10.1007/bf02031706
140 rdf:type schema:CreativeWork
141 sg:pub.10.1007/bf02288325 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035664559
142 https://doi.org/10.1007/bf02288325
143 rdf:type schema:CreativeWork
144 sg:pub.10.1007/bfb0028279 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037242577
145 https://doi.org/10.1007/bfb0028279
146 rdf:type schema:CreativeWork
147 sg:pub.10.1007/bfb0030880 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031077350
148 https://doi.org/10.1007/bfb0030880
149 rdf:type schema:CreativeWork
150 sg:pub.10.1007/bfb0038190 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025966794
151 https://doi.org/10.1007/bfb0038190
152 rdf:type schema:CreativeWork
153 https://app.dimensions.ai/details/publication/pub.1048681974 schema:CreativeWork
154 https://doi.org/10.1002/1520-6750(199204)39:3<399::aid-nav3220390309>3.0.co;2-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043245120
155 rdf:type schema:CreativeWork
156 https://doi.org/10.1002/net.3230070405 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048482235
157 rdf:type schema:CreativeWork
158 https://doi.org/10.1002/net.3230080304 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014134583
159 rdf:type schema:CreativeWork
160 https://doi.org/10.1002/net.3230080306 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007538971
161 rdf:type schema:CreativeWork
162 https://doi.org/10.1002/net.3230080402 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007364680
163 rdf:type schema:CreativeWork
164 https://doi.org/10.1002/net.3230120402 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027837039
165 rdf:type schema:CreativeWork
166 https://doi.org/10.1002/net.3230200302 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013743346
167 rdf:type schema:CreativeWork
168 https://doi.org/10.1002/net.3230230603 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022514573
169 rdf:type schema:CreativeWork
170 https://doi.org/10.1002/net.3230230805 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043795778
171 rdf:type schema:CreativeWork
172 https://doi.org/10.1016/0020-0190(94)90139-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043652978
173 rdf:type schema:CreativeWork
174 https://doi.org/10.1016/0096-3003(94)90126-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043819377
175 rdf:type schema:CreativeWork
176 https://doi.org/10.1016/0166-218x(81)90004-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043047063
177 rdf:type schema:CreativeWork
178 https://doi.org/10.1016/0166-218x(83)90014-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026792880
179 rdf:type schema:CreativeWork
180 https://doi.org/10.1016/0167-8191(93)90089-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035937254
181 rdf:type schema:CreativeWork
182 https://doi.org/10.1016/0196-6774(85)90025-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012376171
183 rdf:type schema:CreativeWork
184 https://doi.org/10.1016/0377-2217(80)90164-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016999432
185 rdf:type schema:CreativeWork
186 https://doi.org/10.1016/0377-2217(92)90317-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053541192
187 rdf:type schema:CreativeWork
188 https://doi.org/10.1016/s0167-8191(05)80155-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011659586
189 rdf:type schema:CreativeWork
190 https://doi.org/10.1090/dimacs/015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1097022677
191 rdf:type schema:CreativeWork
192 https://doi.org/10.1109/43.137519 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061172562
193 rdf:type schema:CreativeWork
194 https://doi.org/10.1109/43.331412 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061173164
195 rdf:type schema:CreativeWork
196 https://doi.org/10.1109/82.204128 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061237597
197 rdf:type schema:CreativeWork
198 https://doi.org/10.1109/asic.1992.270316 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086364481
199 rdf:type schema:CreativeWork
200 https://doi.org/10.1109/sfcs.1984.715935 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086163608
201 rdf:type schema:CreativeWork
202 https://doi.org/10.1109/tct.1966.1082617 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061578302
203 rdf:type schema:CreativeWork
204 https://doi.org/10.1137/0134037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062839697
205 rdf:type schema:CreativeWork
206 https://doi.org/10.1137/0203015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841229
207 rdf:type schema:CreativeWork
208 https://doi.org/10.1137/0216026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841972
209 rdf:type schema:CreativeWork
210 https://doi.org/10.1137/0220060 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842320
211 rdf:type schema:CreativeWork
212 https://doi.org/10.1145/103418.103437 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038049103
213 rdf:type schema:CreativeWork
214 https://doi.org/10.1145/168173.168420 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044687664
215 rdf:type schema:CreativeWork
216 https://doi.org/10.1145/195058.195212 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030898039
217 rdf:type schema:CreativeWork
218 https://doi.org/10.1145/322307.322309 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026688263
219 rdf:type schema:CreativeWork
220 https://doi.org/10.1145/322358.322367 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002375000
221 rdf:type schema:CreativeWork
222 https://doi.org/10.1145/355984.355988 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052782062
223 rdf:type schema:CreativeWork
224 https://doi.org/10.1155/1994/20983 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046824898
225 rdf:type schema:CreativeWork
226 https://doi.org/10.1287/ijoc.1.3.190 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706391
227 rdf:type schema:CreativeWork
228 https://doi.org/10.1287/ijoc.3.4.376 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707391
229 rdf:type schema:CreativeWork
230 https://doi.org/10.1287/opre.38.1.178 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730077
231 rdf:type schema:CreativeWork
232 https://doi.org/10.1287/opre.43.1.130 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730727
233 rdf:type schema:CreativeWork
234 https://www.grid.ac/institutes/grid.170430.1 schema:alternateName University of Central Florida
235 schema:name University of Central Florida, 32816-2362, Orlando, FL, USA
236 rdf:type schema:Organization
 




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


...