Graph Connectivities, Network Coding, and Expander Graphs

We present a new algebraic formulation to compute edge connectivities in a directed graph, using the ideas developed in network coding. This reduces the problem of computing edge connectivities to solving systems of linear equations, thus allowing us to use tools in linear algebra to design new algorithms. Using the algebraic formulation we obtain faster algorithms for computing single source edge connectivities and all pairs edge connectivities, in some settings the amortized time to compute the edge connectivity for one pair is sub linear. Through this connection, we have also found an interesting use of expanders and super concentrators to design fast algorithms for some graph connectivity problems.

Authors

• Ho Yee Cheung
• Lap Chi Lau
• Kai Man Leung

Keywords

• Encoding
• Vectors
• Network coding
• Graph theory
• Polynomials
• Algorithm design and analysis
• Expander Graphs
• System Of Equations
• Directed Graph
• Weak Connections
• Algorithm For Problem
• System Of Linear Equations
• Sublinear
• Single Edge
• Edge Connectivity
• Connectivity Problems
• Algebraic Form
• Undirected
• Linear Time
• Submatrix
• Maximum Degree
• Divide-and-conquer
• Finite Field
• Random Code
• Simple Graph
• Pair Of Edges
• Source Vertex
• Linear Code
• Planar Graphs
• Matrix Inversion Lemma
• Divide-and-conquer Approach
• Global Vector
• Constant Degree
• Well-studied Problem
• Encoding Time