IEICE TRANSACTIONS on Fundamentals
Enumerating Highly-Edge-Connected Spanning Subgraphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1002-1006
- Publication Date
- 2019/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E102.A.1002
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Graph algorithms
Authors
Katsuhisa YAMANAKA
Iwate University
Yasuko MATSUI
Tokai University
Shin-ichi NAKANO
Gunma University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Katsuhisa YAMANAKA, Yasuko MATSUI, Shin-ichi NAKANO, "Enumerating Highly-Edge-Connected Spanning Subgraphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1002-1006, September 2019, doi: 10.1587/transfun.E102.A.1002.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1002/_p
Copy
@ARTICLE{e102-a_9_1002,
author={Katsuhisa YAMANAKA, Yasuko MATSUI, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Enumerating Highly-Edge-Connected Spanning Subgraphs},
year={2019},
volume={E102-A},
number={9},
pages={1002-1006},
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.},
keywords={},
doi={10.1587/transfun.E102.A.1002},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Enumerating Highly-Edge-Connected Spanning Subgraphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1002
EP - 1006
AU - Katsuhisa YAMANAKA
AU - Yasuko MATSUI
AU - Shin-ichi NAKANO
PY - 2019
DO - 10.1587/transfun.E102.A.1002
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - 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.
ER -
English
