Abstract:
We introduce a unified treatment of several edge-connection concepts
of graphs and show how connectivity orientation and connectivity augmentation
results can be extended. It will also presented how classical connectivity
results, such as Edmonds' disjoint arborescence theorem or Nash-Williams'
orientation theorem, can be generalized for hypergraphs. Here are three
concrete corollaries:
1. A 2-edge-connected graph always has a
strongly-connected orientation in which every node, but possibly one, has odd
indegree.
2. Suppose that a bipartite graph G with bipartition S,T has the
property that there are 3k edge-disjoint paths between every two elements of
S. Then there are k edge-disjoint trees so that each contains every
element of S.
3. A graph G has the property that after leaving out any of
its edges the remaining graph contains 2 edge-disjoint spanning trees if and
only if G can be obtained from an initial graph consisting of three parallel
edges connecting two nodes by the following operations (i) add a new edge,
(ii) subdivide an existing edge with a new node v and connect v to an
existing node.
Colloquium - 16 Uhr s.t.
Abstract: Das Nächste Nachbar Problem besteht darin, effiziente Datenstrukturen und Algorithmen zu entwickeln, die zu einer festen Menge P subset R^d von n Punkten und einem beliebigen, spezifizierten Anfragepunkt q in R^d, den oder die nächsten Nachbarn aus P zu q finden. Der Abstand wird meist in einer der Minkowski-Metriken definiert. In zahlreichen Anwendungen, in denen das Problem auftritt, wie zum Beispiel bei ähnlichkeitsanfragen in multimedialen Datenbanken oder bei der Bild- und Mustererkennung, ist die Dimension d des Suchraumes sehr groß, sie liegt oft in der Größenordnung von Hunderten bis Tausenden. Die bis jetzt bekannten Algorithmen für exakte Nächste Nachbar Suche benötigen für Minkowski-Metriken entweder einen in d exponentiellen Speicherplatz oder eine in n fast lineare Suchzeit.
In dem Vortrag werde ich neue eigene Resultate präsentieren.