Computing a Diameter-Constrained Minimum Spanning Tree in Parallel View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2000-02-14

AUTHORS

Narsingh Deo , Ayman Abdalla

ABSTRACT

A minimum spanning tree (MST) with a small diameter is required in numerous practical situations. It is needed, for example, in distributed mutual exclusion algorithms in order to minimize the number of messages communicated among processors per critical section. The Diameter- Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph G with n nodes and a positive integer k, find a spanning tree with the smallest weight among all spanning trees of G which contain no path with more than k edges. This problem is known to be NP- complete, for all values of k; 4 ≤ k ≤ (n − 2). Therefore, one has to depend on heuristics and live with approximate solutions. In this paper, we explore two heuristics for the DCMST problem: First, we present a one-time-tree- construction algorithm that constructs a DCMST in a modified greedy fashion, employing a heuristic for selecting edges to be added to the tree at each stage of the tree construction. This algorithm is fast and easily parallelizable. It is particularly suited when the specified values for k are small—independent of n. The second algorithm starts with an unconstrained MST and iteratively refines it by replacing edges, one by one, in long paths until there is no path left with more than k edges. This heuristic was found to be better suited for larger values of k. We discuss convergence, relative merits, and parallel implementation of these heuristics on the MasPar MP-1 — a massively parallel SIMD machine with 8192 processors. Our extensive empirical study shows that the two heuristics produce good solutions for a wide variety of inputs. More... »

PAGES

17-31

Book

TITLE

Algorithms and Complexity

ISBN

978-3-540-67159-6
978-3-540-46521-8

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-46521-9_2

DOI

http://dx.doi.org/10.1007/3-540-46521-9_2

DIMENSIONS

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


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": [
            "School of Computer Science, 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": [
            "School of Computer Science, University of Central Florida, 32816-2362, Orlando, FL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Abdalla", 
        "givenName": "Ayman", 
        "id": "sg:person.010066537465.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010066537465.29"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0020-0190(92)90219-l", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016548849"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/58564.59295", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047948831"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.1993.253399", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086292083"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icpads.1994.590400", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095402139"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/dimacs/040", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1097022573"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/dimacs/015", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1097022677"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000-02-14", 
    "datePublishedReg": "2000-02-14", 
    "description": "A minimum spanning tree (MST) with a small diameter is required in numerous practical situations. It is needed, for example, in distributed mutual exclusion algorithms in order to minimize the number of messages communicated among processors per critical section. The Diameter- Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph G with n nodes and a positive integer k, find a spanning tree with the smallest weight among all spanning trees of G which contain no path with more than k edges. This problem is known to be NP- complete, for all values of k; 4 \u2264 k \u2264 (n \u2212 2). Therefore, one has to depend on heuristics and live with approximate solutions. In this paper, we explore two heuristics for the DCMST problem: First, we present a one-time-tree- construction algorithm that constructs a DCMST in a modified greedy fashion, employing a heuristic for selecting edges to be added to the tree at each stage of the tree construction. This algorithm is fast and easily parallelizable. It is particularly suited when the specified values for k are small\u2014independent of n. The second algorithm starts with an unconstrained MST and iteratively refines it by replacing edges, one by one, in long paths until there is no path left with more than k edges. This heuristic was found to be better suited for larger values of k. We discuss convergence, relative merits, and parallel implementation of these heuristics on the MasPar MP-1 \u2014 a massively parallel SIMD machine with 8192 processors. Our extensive empirical study shows that the two heuristics produce good solutions for a wide variety of inputs.", 
    "editor": [
      {
        "familyName": "Bongiovanni", 
        "givenName": "Giancarlo", 
        "type": "Person"
      }, 
      {
        "familyName": "Petreschi", 
        "givenName": "Rossella", 
        "type": "Person"
      }, 
      {
        "familyName": "Gambosi", 
        "givenName": "Giorgio", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-46521-9_2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67159-6", 
        "978-3-540-46521-8"
      ], 
      "name": "Algorithms and Complexity", 
      "type": "Book"
    }, 
    "name": "Computing a Diameter-Constrained Minimum Spanning Tree in Parallel", 
    "pagination": "17-31", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-46521-9_2"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "804e0b4b63f4240de9d3f256354d4a159e534776c679cfa52f977ff68d5097c0"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026933360"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-46521-9_2", 
      "https://app.dimensions.ai/details/publication/pub.1026933360"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:32", 
    "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/0000000346_0000000346/records_99815_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-46521-9_2"
  }
]
 

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-46521-9_2'

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-46521-9_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-46521-9_2'

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-46521-9_2'


 

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

100 TRIPLES      23 PREDICATES      32 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-46521-9_2 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nfcf7ed0627c64b58abf1502a16cebb73
4 schema:citation https://doi.org/10.1016/0020-0190(92)90219-l
5 https://doi.org/10.1090/dimacs/015
6 https://doi.org/10.1090/dimacs/040
7 https://doi.org/10.1109/icpads.1994.590400
8 https://doi.org/10.1109/infcom.1993.253399
9 https://doi.org/10.1145/58564.59295
10 schema:datePublished 2000-02-14
11 schema:datePublishedReg 2000-02-14
12 schema:description A minimum spanning tree (MST) with a small diameter is required in numerous practical situations. It is needed, for example, in distributed mutual exclusion algorithms in order to minimize the number of messages communicated among processors per critical section. The Diameter- Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph G with n nodes and a positive integer k, find a spanning tree with the smallest weight among all spanning trees of G which contain no path with more than k edges. This problem is known to be NP- complete, for all values of k; 4 ≤ k ≤ (n − 2). Therefore, one has to depend on heuristics and live with approximate solutions. In this paper, we explore two heuristics for the DCMST problem: First, we present a one-time-tree- construction algorithm that constructs a DCMST in a modified greedy fashion, employing a heuristic for selecting edges to be added to the tree at each stage of the tree construction. This algorithm is fast and easily parallelizable. It is particularly suited when the specified values for k are small—independent of n. The second algorithm starts with an unconstrained MST and iteratively refines it by replacing edges, one by one, in long paths until there is no path left with more than k edges. This heuristic was found to be better suited for larger values of k. We discuss convergence, relative merits, and parallel implementation of these heuristics on the MasPar MP-1 — a massively parallel SIMD machine with 8192 processors. Our extensive empirical study shows that the two heuristics produce good solutions for a wide variety of inputs.
13 schema:editor Ne727e87e4e82484b8502194b0b47efe0
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf Nc450bef4a0d049568718c816fb3b6e5c
18 schema:name Computing a Diameter-Constrained Minimum Spanning Tree in Parallel
19 schema:pagination 17-31
20 schema:productId N71e9535aba9e436ba9f1064bd0dd9421
21 N91335015e5b547009d3980df22f2be8b
22 N9911194404a041f79453bb3338ffee4c
23 schema:publisher N79abca2090014c74ba098c8b5da1d7b7
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026933360
25 https://doi.org/10.1007/3-540-46521-9_2
26 schema:sdDatePublished 2019-04-16T05:32
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N004b68548f7640828e8eb8a6e335a6ed
29 schema:url https://link.springer.com/10.1007%2F3-540-46521-9_2
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N004b68548f7640828e8eb8a6e335a6ed schema:name Springer Nature - SN SciGraph project
34 rdf:type schema:Organization
35 N16b6e1a39d0242d7bb5201aeb31f967c schema:familyName Gambosi
36 schema:givenName Giorgio
37 rdf:type schema:Person
38 N175a8d030998498786355c6f6587c8f5 rdf:first N16b6e1a39d0242d7bb5201aeb31f967c
39 rdf:rest rdf:nil
40 N2c5d2380971b40cb81d98cb6f8c2f0a9 rdf:first sg:person.010066537465.29
41 rdf:rest rdf:nil
42 N71e9535aba9e436ba9f1064bd0dd9421 schema:name dimensions_id
43 schema:value pub.1026933360
44 rdf:type schema:PropertyValue
45 N79abca2090014c74ba098c8b5da1d7b7 schema:location Berlin, Heidelberg
46 schema:name Springer Berlin Heidelberg
47 rdf:type schema:Organisation
48 N8aa530ce7e0245c5a74dba219df87ea8 schema:familyName Bongiovanni
49 schema:givenName Giancarlo
50 rdf:type schema:Person
51 N8cc7fc2e2f4344ec92c33118e4b1d007 rdf:first Nac8d361b31fd43469b98ae73b7b09387
52 rdf:rest N175a8d030998498786355c6f6587c8f5
53 N91335015e5b547009d3980df22f2be8b schema:name readcube_id
54 schema:value 804e0b4b63f4240de9d3f256354d4a159e534776c679cfa52f977ff68d5097c0
55 rdf:type schema:PropertyValue
56 N9911194404a041f79453bb3338ffee4c schema:name doi
57 schema:value 10.1007/3-540-46521-9_2
58 rdf:type schema:PropertyValue
59 Nac8d361b31fd43469b98ae73b7b09387 schema:familyName Petreschi
60 schema:givenName Rossella
61 rdf:type schema:Person
62 Nc450bef4a0d049568718c816fb3b6e5c schema:isbn 978-3-540-46521-8
63 978-3-540-67159-6
64 schema:name Algorithms and Complexity
65 rdf:type schema:Book
66 Ne727e87e4e82484b8502194b0b47efe0 rdf:first N8aa530ce7e0245c5a74dba219df87ea8
67 rdf:rest N8cc7fc2e2f4344ec92c33118e4b1d007
68 Nfcf7ed0627c64b58abf1502a16cebb73 rdf:first sg:person.010274011142.47
69 rdf:rest N2c5d2380971b40cb81d98cb6f8c2f0a9
70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
71 schema:name Information and Computing Sciences
72 rdf:type schema:DefinedTerm
73 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
74 schema:name Computation Theory and Mathematics
75 rdf:type schema:DefinedTerm
76 sg:person.010066537465.29 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
77 schema:familyName Abdalla
78 schema:givenName Ayman
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010066537465.29
80 rdf:type schema:Person
81 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
82 schema:familyName Deo
83 schema:givenName Narsingh
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
85 rdf:type schema:Person
86 https://doi.org/10.1016/0020-0190(92)90219-l schema:sameAs https://app.dimensions.ai/details/publication/pub.1016548849
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1090/dimacs/015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1097022677
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1090/dimacs/040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1097022573
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1109/icpads.1994.590400 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095402139
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1109/infcom.1993.253399 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086292083
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1145/58564.59295 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047948831
97 rdf:type schema:CreativeWork
98 https://www.grid.ac/institutes/grid.170430.1 schema:alternateName University of Central Florida
99 schema:name School of Computer Science, University of Central Florida, 32816-2362, Orlando, FL, USA
100 rdf:type schema:Organization
 




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


...