TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. A cut tree representation for pendant pairs
 
Options

A cut tree representation for pendant pairs

Publikationstyp
Conference Paper
Date Issued
2018-12
Sprache
English
Author(s)
Lo, On-Hei Solomon  
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7605
First published in
Leibniz international proceedings in informatics (LIPIcs)  
Number in series
123
Article Number
38
Citation
29th International Symposium on Algorithms and Computation (ISAAC 2018) 123: 38 (2018)
Contribution to Conference
International Symposium on Algorithms and Computation (ISAAC 2018)  
Publisher DOI
10.4230/LIPIcs.ISAAC.2018.38
Scopus ID
2-s2.0-85063690337
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
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback