Logo der Fakultät Logo LG Theoretische Informatik




AutorInnen: Lena Schlipf
Jens M. Schmidt
Kategorie: Sonstiges
erschienen in: CoRR, Vol. abs/1607.04431, 2016

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 concept behind all these orders has been shown: they can be described by a graph decomposition 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 paper, we establish 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. While the former can be seen as the edge-variants of st-numberings, the latter are the edge-variants of Mondshein sequences and non-separating ear decompositions. The methods that we use for obtaining such edge-orders differ considerably in almost all details from the ones used for their vertex-counterparts, as different graph-theoretic constructions are used in the inductive proof and standard reductions from edge- to vertex-connectivity are bound to fail.
As a first application, we 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 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.

Download: arXiv Website
BibTeX-Eintrag: @article{, author = {Lena Schlipf and Jens M. Schmidt}, title = {Edge-Orders}, journal = {CoRR}, volume = {abs/1607.04431}, year = {2016}, url = {http://arxiv.org/abs/1607.04431}, }
Christoph Doppelbauer | 05.05.2017
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen