Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus

2010/04/26 by Viresh Patel, Patel, Viresh
Computer Science · Materials Science · #Interconnection Networks and Systems #Nanocluster Synthesis and Applications #Graphene research and applications

paper · pdf · doi:10.48550/arxiv.1004.4484

Abstract

In this paper, we show that for an n-vertex graph G of genus g, the edge expansion of G can be determined in time n^O(g2). We show that the same is true for various other similar measures of edge connectivity.

Related

• Edge connectivity in graphs: an expansion theorem
• A Simple Deterministic Algorithm for Edge Connectivity
• The Complexity of Approximating Vertex Expansion
• Extremality and Sharp Bounds for the k-edge-connectivity of Graphs
• Gonality of Expander Graphs