Graph Connectivities, Network Coding, and Expander Graphs

DOI10.1109/FOCS.2011.55MaRDI QIDQ5494964zbMATH OpenFDO

Authors Ho Yee Cheung, Lap Chi Lau, Kai Man Leung

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2011.55

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(6)

• Efficient algorithm for computing all low s-t edge connectivities in directed graphs
• On element-connectivity preserving graph simplification
• On approximating matrix norms in data streams
• Algorithms for weighted matching generalizations. I: Bipartite graphs, b-matching, and unweighted f-factors
• Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)
• Hardness of graph-structured algebraic and symbolic problems

This page was built for publication: Graph Connectivities, Network Coding, and Expander Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494964)