科研之友
微信
新浪微博
Facebook
分享链接
摘要
In this paper, we give the first polynomial-time algorithm for determining the edge expansion for a graph of fixed orientable genus. We show that for a multigraph G with m edges and orientable genus g, the edge expansion of G can be determined in time m(O(g)). We show that the same is true for various other similar measures of edge connectivity.
- 出版日期2013
