Tarjan, Algorithmus von - Lexikon der Mathematik

Lexikon der Mathematik: Tarjan, Algorithmus von

berechnet in einem zusammenhängenden GraphenG alle trennenden Ecken und alle Blöcke von G.

Dieser Algorithmus von R.E. Tarjan aus dem Jahre 1972 besitzt die Komplexität O(|K(G)|).

Copyright Springer Verlag GmbH Deutschland 2017

Die Autoren

- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Artikel zum Thema

Medienwirkungsforschung: Immer mehr Morde in Filmen

Nicht nur Krimis, sondern alle Arten von Filmen drehen sich zunehmend um Mord und Totschlag. Das zeigt eine KI-Analyse von Dialogen aus den vergangenen 50 Jahren.

Kombinatorik: Mathematische Überraschung beim Schach

Ein Springer bewegt sich schneller über das Schachbrett als ein König. Aber wie viel schneller? Die Antwort hängt erstaunlicherweise mit den Fibonacci-Zahlen zusammen.

Eulbergs tönende Tierwelt: Zitronengelber Gast am winterlichen Futterhaus

Nicht nur mit ihrem knalligen Federkleid beeindruckt die Goldammer – ihr prägnantes Lied inspirierte wahrscheinlich schon Beethoven.

»Die kosmische Krise«: Der Mythos lebt

Unzählige Ufo-Sichtungen, aber noch kein echter Kommunikationsversuch – stehen wir womöglich kurz vor einem Erstkontakt? Daniel Gerritzen entwirft ein Szenario. Eine Rezension

Themenkanäle

Das Digital-Manifest

Algorithmen, Nudging, Big Data - unser Leben wird zunehmend digitaler. Doch viele Menschen sind darauf nicht vorbereitet. Daher benötigen wir klare Regeln. Ein Appell.

Zahlentheorie

Neben den natürlichen Zahlen, die uns schon in der Grundschule begegnen, gibt es etliche andere Zahlensysteme. Einige von ihnen werfen spannende Fragen auf.

Die neue Generation von Computern

Erste Prototypen von Quantencomputern gibt es bereits. Was wird sich mit den Prozessoren ändern, die auf Quantenmechanik basieren? Sind Daten dann noch sicher? Eine Themenseite

SponsoredPartnerinhalte