Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Optimization of the Values of the Right-Hand Sides of Boundary Conditions with Point and Integral Terms for the ODE System Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

A Given Diameter MST on a Random Graph

verfasst von : Edward K. Gimadi, Aleksandr S. Shevyakov, Alexandr A. Shtepa

Erschienen in: Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We give a new approximation polynomial time algorithm for one of the intractable problem of finding given-diameter Minimum Spanning Tree (MST) on n-vertex complete graph with randomly weighted edges. A significant advantage of this algorithm is that it turned out to be well suited for finding several edge-disjoint MST of a given diameter. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an segment \([a_n; b_n]\), \(a_n>0\). Sufficient conditions of asymptotic optimality are presented. It is also noteworthy that the new algorithmic approach to solve the problem of finding a given-diameter MST both on directed and undirected graphs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel P-Regularity Theory: Applications to Optimization
Nächstes Kapitel Method of Parametric Correction in Data Transformation and Approximation Problems
Literatur
1.
Angel, O., Flaxman, A.D., Wilson, D.B.: A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks. arXiv:​0810.​4908v2 [math.PR] (2011)
2.
Cooper, C., Frieze, A., Ince, N., Janson, S., Spencer, J.: On the length of a random minimum spanning tree. Comb. Probab. Comput. 25(1), 89–107 (2016)MathSciNetCrossRef
3.
4.
Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco (1979)MATH
5.
Gimadi, E.K., Glebov, N.I., Perepelitsa, V.A.: Algorithms with estimates for discrete optimization problems. Problemy Kibernetiki 31, 35–42 (1975) (in Russian)
6.
Gimadi, E.K., Istomin, A., Shin, E.: On algorithm for the minimum spanning tree problem bounded below. In: Proceedings of DOOR 2016, Vladivostok, Russia, 19–23 September 2016, vol. 1623, pp. 11–17. CEUR-WS (2016)
7.
Gimadi, E.K., Istomin, A.M., Shin, E.Y.: On given diameter MST problem on random instances. In: CEUR Workshop Proceedings 2018, pp. 159–168 (2019)
8.
Gimadi, E.K., Serdyukov, A.I.: A probabilistic analysis of an approximation algorithm for the minimum weight spanning tree problem with bounded from below diameter. In: Inderfurth, K., Schwödiauer, G., Domschke, W., Juhnke, F., Kleinschmidt, P., Wäascher, G. (eds.) Operations Research Proceedings 1999. ORP, vol. 1999, pp. 63–68. Springer, Heidelberg (2000). https://​doi.​org/​10.​1007/​978-3-642-58300-1_​12CrossRef
9.
Gimadi, E., Shevyakov, A., Shin, E.: Asymptotically optimal approach to a given diameter undirected MST problem on random instances. In: Proceedings of 15-th International Asian School-Seminar “Optimization Problems of Complex System” (OPCS-2019), Novosibirsk, Akademgorodok, Russia, 26–30 August 2019, pp. 48–52. IEEE Xplore (2019). https://​doi.​org/​10.​1109/​OPCS.​2019.​8880223
10.
11.
12.
Petrov, V.V.: Limit Theorems of Probability Theory. Sequences of Independent Random Variables. Clarendon Press, Oxford, 304 p. (1995)
Metadaten
Titel
A Given Diameter MST on a Random Graph
verfasst von
Edward K. Gimadi
Aleksandr S. Shevyakov
Alexandr A. Shtepa
Copyright-Jahr
2020
Buch
Optimization and Applications

Print ISBN: 978-3-030-62866-6

Electronic ISBN: 978-3-030-62867-3

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-62867-3_9

Premium Partner

    Bildnachweise