Abstract | ||
---|---|---|
In this paper, we consider the problem of enumerating spanning subgraphs with high edge-connectivity of an input graph. Such subgraphs ensure multiple routes between two vertices. We first present an algorithm that enumerates all the 2-edge-connected spanning subgraphs of a given plane graph with n vertices. The algorithm generates each 2-edge-connected spanning subgraph of the input graph in O(n) time. We next present an algorithm that enumerates all the k-edge-connected spanning subgraphs of a given general graph with m edges. The algorithm generates each k-edge-connected spanning subgraph of the input graph in O(mT) time, where T is the running time to check the k-edge-connectivity of a graph. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1587/transfun.E102.A.1002 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
enumeration, algorithm, spanning subgraph, edge-connectivity | Discrete mathematics,Mathematics | Journal |
Volume | Issue | ISSN |
E102A | 9 | 0916-8508 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Katsuhisa Yamanaka | 1 | 60 | 15.73 |
Yasuko Matsui | 2 | 62 | 7.16 |
Shin-ichi Nakano | 3 | 246 | 24.40 |