Network coding in undirected graphs is either very helpful or not helpful at all

DOI10.4230/LIPIcs.ITCS.2017.18zbMath1402.90030arXiv1608.06545MaRDI QIDQ4638067

Sumegha Garg, Ariel Schvartzman, Mark Braverman

Publication date: 3 May 2018

Full work available at URL: https://arxiv.org/abs/1608.06545

zbMATH Keywords

multicommodity flowsnetwork codinggap amplification

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Source coding (94A29) Graph operations (line graphs, products, etc.) (05C76) Flows in graphs (05C21)

Related Items (3)

Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ Lower Bounds for External Memory Integer Sorting via Network Coding ⋮ Lower Bounds for Multiplication via Network Coding

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs of prescribed girth and bi-degree
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Network Coding Applications
• Network information flow
• Lexicographic Products and the Power of Non-linear Network Coding
• On the capacity of information networks

This page was built for publication: Network coding in undirected graphs is either very helpful or not helpful at all