Low diameter graph decompositions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-12

AUTHORS

Nathan Linial, Michael Saks

ABSTRACT

Adecomposition of a graphG=(V,E) is a partition of the vertex set into subsets (calledblocks). Thediameter of a decomposition is the leastd such that any two vertices belonging to the same connected component of a block are at distance ≤d. In this paper we prove (nearly best possible) statements, of the form: Anyn-vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [4] it was shown that every graph has a decomposition into at mosts(n) blocks of diameter at mosts(n) for\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$s(n) = n^{O(\sqrt {\log \log n/\log n)} }$$ \end{document}. Using a technique of Awerbuch [3] and Awerbuch and Peleg [5], we improve this result by showing that every graph has a decomposition of diameterO (logn) intoO(logn) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in timeO(log2n). The construction can be parameterized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible, for two families of graphs: the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner's lemma for the first class and Tucker's lemma for the second. More... »

PAGES

441-454

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, The Hebrew University, 91904, Jerusalem, Israel", 
          "id": "http://www.grid.ac/institutes/grid.9619.7", 
          "name": [
            "Department of Computer Science, The Hebrew University, 91904, Jerusalem, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Linial", 
        "givenName": "Nathan", 
        "id": "sg:person.015760032537.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, UCSD, 92 122, La Jolla, CA", 
          "id": "http://www.grid.ac/institutes/grid.266100.3", 
          "name": [
            "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ", 
            "Department of Computer Science and Engineering, UCSD, 92 122, La Jolla, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-56188-9_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030975968", 
          "https://doi.org/10.1007/3-540-56188-9_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02765904", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053329812", 
          "https://doi.org/10.1007/bf02765904"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-50327-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021219610", 
          "https://doi.org/10.1007/978-3-642-50327-6"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1993-12", 
    "datePublishedReg": "1993-12-01", 
    "description": "Adecomposition of a graphG=(V,E) is a partition of the vertex set into subsets (calledblocks). Thediameter of a decomposition is the leastd such that any two vertices belonging to the same connected component of a block are at distance \u2264d. In this paper we prove (nearly best possible) statements, of the form: Anyn-vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [4] it was shown that every graph has a decomposition into at mosts(n) blocks of diameter at mosts(n) for\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$s(n) = n^{O(\\sqrt {\\log \\log n/\\log n)} }$$\n\\end{document}. Using a technique of Awerbuch [3] and Awerbuch and Peleg [5], we improve this result by showing that every graph has a decomposition of diameterO (logn) intoO(logn) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in timeO(log2n). The construction can be parameterized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible, for two families of graphs: the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner's lemma for the first class and Tucker's lemma for the second.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01303516", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "13"
      }
    ], 
    "keywords": [
      "families of graphs", 
      "certain triangulations", 
      "combinatorial topology", 
      "same connected component", 
      "grid graphs", 
      "basic results", 
      "graph decomposition", 
      "lemma", 
      "Sperner's lemma", 
      "Tucker\u2019s lemma", 
      "such decompositions", 
      "graph", 
      "number of blocks", 
      "connected components", 
      "vertices", 
      "first class", 
      "decomposition", 
      "Awerbuch", 
      "computation", 
      "small number", 
      "diagonals", 
      "topology", 
      "algorithm", 
      "proof", 
      "class", 
      "simplex", 
      "partition", 
      "number", 
      "first consists", 
      "block", 
      "triangulation", 
      "Peleg", 
      "tool", 
      "results", 
      "distance", 
      "technique", 
      "construction", 
      "small diameter", 
      "form", 
      "subset", 
      "consist", 
      "cases", 
      "statements", 
      "components", 
      "diameter", 
      "family", 
      "addition", 
      "skeleton", 
      "paper", 
      "thediameter"
    ], 
    "name": "Low diameter graph decompositions", 
    "pagination": "441-454", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035669408"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01303516"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01303516", 
      "https://app.dimensions.ai/details/publication/pub.1035669408"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:29", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_236.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01303516"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

130 TRIPLES      21 PREDICATES      78 URIs      67 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01303516 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N028a336c27724b72ac271e2a405b3115
4 schema:citation sg:pub.10.1007/3-540-56188-9_1
5 sg:pub.10.1007/978-3-642-50327-6
6 sg:pub.10.1007/bf02765904
7 schema:datePublished 1993-12
8 schema:datePublishedReg 1993-12-01
9 schema:description Adecomposition of a graphG=(V,E) is a partition of the vertex set into subsets (calledblocks). Thediameter of a decomposition is the leastd such that any two vertices belonging to the same connected component of a block are at distance ≤d. In this paper we prove (nearly best possible) statements, of the form: Anyn-vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [4] it was shown that every graph has a decomposition into at mosts(n) blocks of diameter at mosts(n) for\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$s(n) = n^{O(\sqrt {\log \log n/\log n)} }$$ \end{document}. Using a technique of Awerbuch [3] and Awerbuch and Peleg [5], we improve this result by showing that every graph has a decomposition of diameterO (logn) intoO(logn) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in timeO(log2n). The construction can be parameterized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible, for two families of graphs: the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner's lemma for the first class and Tucker's lemma for the second.
10 schema:genre article
11 schema:isAccessibleForFree false
12 schema:isPartOf N0139def4e6934c5493a38996cb6c7485
13 N04c61fb5bf174e61b37a126b89840e39
14 sg:journal.1136493
15 schema:keywords Awerbuch
16 Peleg
17 Sperner's lemma
18 Tucker’s lemma
19 addition
20 algorithm
21 basic results
22 block
23 cases
24 certain triangulations
25 class
26 combinatorial topology
27 components
28 computation
29 connected components
30 consist
31 construction
32 decomposition
33 diagonals
34 diameter
35 distance
36 families of graphs
37 family
38 first class
39 first consists
40 form
41 graph
42 graph decomposition
43 grid graphs
44 lemma
45 number
46 number of blocks
47 paper
48 partition
49 proof
50 results
51 same connected component
52 simplex
53 skeleton
54 small diameter
55 small number
56 statements
57 subset
58 such decompositions
59 technique
60 thediameter
61 tool
62 topology
63 triangulation
64 vertices
65 schema:name Low diameter graph decompositions
66 schema:pagination 441-454
67 schema:productId N831695ff452043c0a227e4664202c1ad
68 Nb280b4cd8172403a9f931fc26851a3b5
69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035669408
70 https://doi.org/10.1007/bf01303516
71 schema:sdDatePublished 2022-10-01T06:29
72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
73 schema:sdPublisher N4fa1ff82ddbc4998aab2b46d9679c325
74 schema:url https://doi.org/10.1007/bf01303516
75 sgo:license sg:explorer/license/
76 sgo:sdDataset articles
77 rdf:type schema:ScholarlyArticle
78 N0139def4e6934c5493a38996cb6c7485 schema:volumeNumber 13
79 rdf:type schema:PublicationVolume
80 N028a336c27724b72ac271e2a405b3115 rdf:first sg:person.015760032537.47
81 rdf:rest N24291a1ab61d48a1b5da696ea5e9cca5
82 N04c61fb5bf174e61b37a126b89840e39 schema:issueNumber 4
83 rdf:type schema:PublicationIssue
84 N24291a1ab61d48a1b5da696ea5e9cca5 rdf:first sg:person.011520224512.05
85 rdf:rest rdf:nil
86 N4fa1ff82ddbc4998aab2b46d9679c325 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N831695ff452043c0a227e4664202c1ad schema:name doi
89 schema:value 10.1007/bf01303516
90 rdf:type schema:PropertyValue
91 Nb280b4cd8172403a9f931fc26851a3b5 schema:name dimensions_id
92 schema:value pub.1035669408
93 rdf:type schema:PropertyValue
94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
95 schema:name Information and Computing Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
98 schema:name Computation Theory and Mathematics
99 rdf:type schema:DefinedTerm
100 sg:journal.1136493 schema:issn 0209-9683
101 1439-6912
102 schema:name Combinatorica
103 schema:publisher Springer Nature
104 rdf:type schema:Periodical
105 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.266100.3
106 schema:familyName Saks
107 schema:givenName Michael
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
109 rdf:type schema:Person
110 sg:person.015760032537.47 schema:affiliation grid-institutes:grid.9619.7
111 schema:familyName Linial
112 schema:givenName Nathan
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47
114 rdf:type schema:Person
115 sg:pub.10.1007/3-540-56188-9_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030975968
116 https://doi.org/10.1007/3-540-56188-9_1
117 rdf:type schema:CreativeWork
118 sg:pub.10.1007/978-3-642-50327-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021219610
119 https://doi.org/10.1007/978-3-642-50327-6
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/bf02765904 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053329812
122 https://doi.org/10.1007/bf02765904
123 rdf:type schema:CreativeWork
124 grid-institutes:grid.266100.3 schema:alternateName Department of Computer Science and Engineering, UCSD, 92 122, La Jolla, CA
125 schema:name Department of Computer Science and Engineering, UCSD, 92 122, La Jolla, CA
126 Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ
127 rdf:type schema:Organization
128 grid-institutes:grid.9619.7 schema:alternateName Department of Computer Science, The Hebrew University, 91904, Jerusalem, Israel
129 schema:name Department of Computer Science, The Hebrew University, 91904, Jerusalem, Israel
130 rdf:type schema:Organization
 




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


...