The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Kertas kerja ini membincangkan masalah menyenaraikan subgraf rentang bersambung 3 tepi bagi graf satah input. Pada 2018, Yamanaka et al. mencadangkan dua algoritma penghitungan untuk masalah tersebut. Algoritma mereka menjana setiap subgraf span bersambung 2 tepi bagi graf satah tertentu dengan n bucu dalam O(n) masa, dan satu lagi menjana setiap satu k-subgraf rentang bersambung tepi bagi graf umum dengan m tepi dalam O(mT) masa, di mana T adalah masa berjalan untuk menyemak k-kesambungan tepi graf. Kertas ini memfokuskan pada kes sambungan 3-tepi dalam graf satah. Kami memberikan algoritma yang menjana setiap subgraf rentang 3 tepi yang disambungkan bagi graf satah input dalam O(n2) masa. Kerumitan masa ini adalah sama seperti algoritma oleh Yamanaka et al., tetapi algoritma kami lebih mudah daripada algoritma mereka.
Yasuko MATSUI
Tokai University
Kenta OZEKI
Yokohama National University
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.
Salinan
Yasuko MATSUI, Kenta OZEKI, "A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 3, pp. 389-391, March 2021, doi: 10.1587/transinf.2020FCL0002.
Abstract: This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with n vertices in O(n) time, and another one generates each k-edge-connected spanning subgraph of a general graph with m edges in O(mT) time, where T is the running time to check the k-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in O(n2) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020FCL0002/_p
Salinan
@ARTICLE{e104-d_3_389,
author={Yasuko MATSUI, Kenta OZEKI, },
journal={IEICE TRANSACTIONS on Information},
title={A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs},
year={2021},
volume={E104-D},
number={3},
pages={389-391},
abstract={This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with n vertices in O(n) time, and another one generates each k-edge-connected spanning subgraph of a general graph with m edges in O(mT) time, where T is the running time to check the k-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in O(n2) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.},
keywords={},
doi={10.1587/transinf.2020FCL0002},
ISSN={1745-1361},
month={March},}
Salinan
TY - JOUR
TI - A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 389
EP - 391
AU - Yasuko MATSUI
AU - Kenta OZEKI
PY - 2021
DO - 10.1587/transinf.2020FCL0002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2021
AB - This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with n vertices in O(n) time, and another one generates each k-edge-connected spanning subgraph of a general graph with m edges in O(mT) time, where T is the running time to check the k-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in O(n2) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.
ER -