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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On the Capture Time of Cops and Robbers Game on a Planar Graph Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound

verfasst von : Sung Eun Bae, Tong-Wook Shinn, Tadao Takaoka

Erschienen in: Combinatorial 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 break the long standing cubic time bound of \(O(n^3)\) for the Minimum Weight Polygon Triangulation problem by showing that the well known dynamic programming algorithm, reported independently by Gilbert and Klincsek, can be optimized with a faster algorithm for the \((min,+)\)-product using look-up tables. In doing so, we also show that the well known Floyd-Warshall algorithm can be optimized in a similar manner to achieve a sub-cubic time bound for the All Pairs Shortest Paths problem without having to resort to recursion in the semi-ring theory.

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 Performing Multicut on Walkable Environments
Nächstes Kapitel The Mixed Center Location Problem
Fußnoten
1
Named after the Belgian mathematician Eugene Charles Catalan (1814–1894).
 
Literatur
1.
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston (1974)MATH
2.
Atallah, M.J., Callahan, P.B., Goodrich, M.T.: P-complete geometric problems. Int. J. Comput. Geom. Appl. 3, 443–462 (1993)MathSciNetCrossRefMATH
3.
Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. In: FOCS, pp. 569–575 (1991)
4.
5.
Dobosiewicz, W.: A more efficient algorithm for the min-plus multiplication. Int. J. Comput. Math. 32, 49–60 (1990)CrossRefMATH
6.
Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)CrossRef
7.
8.
Gilbert, P.D.: New results on planar triangulations. Report R-850, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois (1979)
9.
10.
Han, Y.: An \(O(n^{3}(\log {\log {n}}/\log {n})^{5/4})\) time algorithm for all pairs shortest path. Algorithmica 51, 428–434 (2008)MathSciNetCrossRefMATH
11.
Han, Y., Takaoka, T.: An \(O(n^{3}\log {\log {n}}/\log ^{2}{n})\) time algorithm for all pairs shortest paths. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 131–141. Springer, Heidelberg (2012)CrossRef
12.
13.
Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51, 400–403 (1995)MathSciNetCrossRefMATH
14.
Takaoka, T.: A new upper bound on the complexity of the all pairs shortest path problem. Inf. Process. Lett. 43, 195–199 (1992)MathSciNetCrossRefMATH
15.
Takaoka, T.: An \(O(n^{3}\log {\log {n}}/\log {n})\) time algorithm for the all-pairs shortest path problem. Inf. Process. Lett. 96, 155–161 (2005)MathSciNetCrossRefMATH
16.
17.
Zwick, U.: A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. Algorithmica 46, 181–192 (2006)MathSciNetCrossRefMATH
Metadaten
Titel
Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
verfasst von
Sung Eun Bae
Tong-Wook Shinn
Tadao Takaoka
Copyright-Jahr
2016
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-48748-9

Electronic ISBN: 978-3-319-48749-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-48749-6_24