Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Certified Machine-Learning Models Read chapter Read first chapter

2020 | OriginalPaper | Chapter

Simple Distributed Spanners in Dense Congest Networks

Authors : Leonid Barenboim, Tzalik Maimon

Published in: SOFSEM 2020: Theory and Practice of Computer Science

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The problem of computing a sparse spanning subgraph is a well-studied problem in the distributed setting, and a lot of research was done in the direction of computing spanners or solving the more relaxed problem of connectivity. Still, efficiently constructing a linear-size spanner deterministically remains a challenging open problem even in specific topologies.
In this paper we provide several simple spanner constructions of linear size, for various graph families. Our first result shows that the connectivity problem can be solved deterministically using a linear size spanner within constant running time on graphs with bounded neighborhood independence. This is a very wide family of graphs that includes unit-disk graphs, unit-ball graphs, line graphs, claw-free graphs and many others. Moreover, our algorithm works in the \(\mathcal {CONGEST}\) model. It also immediately leads to a constant time deterministic solution for the connectivity problem in the Congested-Clique.
Our second result provides a linear size spanner in the \(\mathcal {CONGEST}\) model for graphs with bounded diversity. This is a subtype of graphs with bounded neighborhood independence that captures various types of networks, such as wireless networks and social networks. Here too our result has constant running time and is deterministic. Moreover, the latter result has an additional desired property of a small stretch.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
next chapter The Order Type of Scattered Context-Free Orderings of Rank One Is Computable
Footnotes
1
Diversity can be also defined with respect to a clique cover of a given graph. Then, the diversity of a vertex is the number of maximal cliques in the cover that the vertex belongs to. In this paper, however, we do not employ clique covers, and so the diversity is defined as the number of maximal cliques in the input graph.
 
Literature
1.
Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear cost sequential and distribured constructions of sparse neighborhood covers. In: FOCS 1993, pp. 638–647 (1993)
2.
Barenboim, L., Elkin, M.: Distributed deterministic edge coloring using bounded neighborhood independence. Distrib. Comput. 26(5–6), 273–287 (2013)CrossRef
3.
4.
Barenboim, L., Elkin, M., Maimon, T.: Deterministic distributed \((\varDelta + o(\varDelta ))\)-edge-coloring, and vertex-coloring of graphs with bounded diversity. In: PODC 2017, pp. 175–184 (2017)
5.
Barenboim, L., Maimon, T.: Distributed symmetry breaking in graphs with bounded diversity. In: IPDPS 2018, 723–732 (2018)
6.
Baswana, S., Sen, S.: A simple linear time algorithm for computing a \((2k - 1)\)-spanner of \({O}({n}^{1+1/{k}})\) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 384–396. Springer, Heidelberg (2003). https://​doi.​org/​10.​1007/​3-540-45061-0_​32CrossRef
7.
Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: On the locality of distributed sparse spanner construction. In: PODC 2008, pp. 273–282 (2008)
8.
Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. In: FOCS, pp. 452–461 (1996)
9.
Derbel, B., Mosbah, M., Zemmari, A.: Sublinear fully distributed partition with applications. Theory Comput. Syst. 47(2), 368–404 (2010)MathSciNetCrossRef
10.
11.
Erdos, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications. Proceedings of Symposium Smolenice, pp. 29–36 (1963)
12.
Elkin, M., Peleg, D.: \((1 + \epsilon ,\beta )\)-spanner constructions for general graphs. In: STOC 2001, pp. 173–182 (2001)
13.
Grossman, O., Parter, M.: Improved deterministic distributed construction of spanners. In: DISC 2017, 24:1–24:16 (2017)
14.
Hegeman, J.W., Pandurangan, G., Pemmaraju, S.V., Sardeshmukh, V.B., Scquizzato, M.: Toward optimal bounds in the congested clique: graph connectivity and MST. In: PODC 2015, pp. 91–100 (2015)
15.
16.
17.
18.
Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In: PODC 2013, pp. 42–50 (2013)
19.
Lotker, Z., Pavlov, E., Patt-Shamir, B., Peleg, D.: MST construction in \(O(\log \log n)\) communication rounds. In: SPAA 2003, pp. 94–100 (2003)
20.
Peleg, D.: Distributed computing: a locality-sensitive approach. In: SIAM 2000 (2000)
21.
22.
Peleg, D., Solomon, S.: Dynamic \((1+\epsilon )\)-approximate matchings: a density-sensitive approach. In: SODA 2016, pp. 712–729 (2016)
23.
Peleg, D., Ullman, J.: An optimal synchronizer for the hypercube. In: PODC, pp. 77–85 (1987)
24.
Schneider, J., Wattenhofer, R.: A log-star distributed Maximal Independent Set algorithm for Growth Bounded Graphs. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, pp. 35–44 (2008)
25.
Woodruff, D.P.: Lower bounds for additive spanners, emulators, and more. In: FOCS 2006, pp. 389–398 (2006)
Metadata
Title
Simple Distributed Spanners in Dense Congest Networks
Authors
Leonid Barenboim
Tzalik Maimon
Copyright Year
2020
Book
SOFSEM 2020: Theory and Practice of Computer Science

Print ISBN: 978-3-030-38918-5

Electronic ISBN: 978-3-030-38919-2

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-38919-2_22

Premium Partner

    Image Credits