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 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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/s00453-018-0516-4 | ICALP |
Keywords | DocType | Volume |
Edge-order,St-edge-order,Canonical ordering,Edge-independent spanning tree,Mondshein sequence,Non-separating ear decomposition,3-Edge-connected graphs,Linear time | Conference | abs/1607.04431 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lena Schlipf | 1 | 18 | 5.79 |
Jens M. Schmidt | 2 | 0 | 1.69 |