2008/05/27 by Guangyue Han, Han, Guangyue · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.0805.4059
openalex publication_date 2008/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For an acyclic directed graph with multiple sources and multiple sinks, we prove that one can choose the Merger's paths between the sources and the sinks such that the number of mergings between these paths is upper bounded by a constant depending only on the min-cuts between the sources and the sinks, regardless of the size and topology of the graph. We also give bounds on the minimum number of mergings between these paths, and discuss how it depends on the min-cuts.