Logo der Freien Universität BerlinFreie Universität Berlin

Fachbereich Mathematik und Informatik


Service-Navigation

  • Startseite
  • Personen
  • Impressum
  • Sitemap
  • Kontakt
  • Datenschutz
DE
  • DE: Deutsch
  • EN: English
Hinweise zur Datenübertragung bei der Google™ Suche
Fachbereich Mathematik und Informatik/

Institut für Informatik

Menü
  • Institut

    loading...

  • Studium

    loading...

  • Forschung

    loading...

  • Termine

    loading...

  • Service

    loading...

Mikronavigation

  • Startseite
  • Informatik
  • Termine
  • Vortrag + Lehrprobe von Dr. Lena Schlipf

Dr. Lena Schlipf: “Edge-Orders”

17.01.2018 | 16:15 - 17:45

Vortrag + Lehrprobe im Rahmen der JP-Besetzung "Theoretische Informatik (Algorithmik)".

Dr. Lena Schlipf, Hagen

“Edge-Orders”

Abstract:
Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying link behind all these orders has been shown that links them to well-known graph decompositions into parts that have a prescribed vertex-connectivity.
                Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edge-connectivity. In this talk, I will present such a concept named edge-orders and show how to compute (1,1)-edge-orders of 2-edge-connected graphs as well as (2,1)-edge-orders of 3-edge-connected graphs in linear time, respectively.
As a first application, we will consider the famous Edge-Independent Spanning Tree Conjecture, which asserts that every k-edge-connected graph contains k rooted spanning trees that are pairwise edge-independent. We will illustrate the impact of the above edge-orders by deducing algorithms that construct 2- and 3-edge independent spanning trees of 2- and 3-edge-connected graphs, the latter of which improves the best known running time from O(n^2) to linear time.

(This is joint work with Jens M. Schmidt.)

Zeit & Ort

17.01.2018 | 16:15 - 17:45

Takustr. 9, SR 053

spinner

Informatik Nachrichten

spinner

Service-Navigation

  • Startseite
  • Personen
  • Impressum
  • Sitemap
  • Kontakt
  • Datenschutz

Diese Seite

  • Drucken
  • RSS-Feed abonnieren
  • English