Options
A cut tree representation for pendant pairs
Publikationstyp
Conference Paper
Date Issued
2018-12
Sprache
English
Author(s)
TORE-URI
First published in
Number in series
123
Article Number
38
Citation
29th International Symposium on Algorithms and Computation (ISAAC 2018) 123: 38 (2018)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
Two vertices v and w of a graph G are called a pendant pair if the maximal number of edge-disjoint paths in G between them is precisely mind(v), d(w), where d denotes the degree function. The importance of pendant pairs stems from the fact that they are the key ingredient in one of the simplest and most widely used algorithms for the minimum cut problem today. Mader showed 1974 that every simple graph with minimum degree δ contains Ω(δ2) pendant pairs; this is the best bound known so far. We improve this result by showing that every simple graph G with minimum degree δ ≥ 5 or with edge-connectivity λ ≥ 4 or with vertex-connectivity κ ≥ 3 contains in fact Ω(δ|V |) pendant pairs. We prove that this bound is tight from several perspectives, and that Ω(δ|V |) pendant pairs can be computed efficiently, namely in linear time when a Gomory-Hu tree is given. Our method utilizes a new cut tree representation of graphs.
Subjects
And phrases Pendant Pairs
Gomory-Hu Tree
Maximal Adjacency Ordering
Maximum Cardinality Search
Pendant Tree
Testing Edge-Connectivity