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
Diberi graf G, puncak yang ditetapkan r dan nombor asli k, kami ingin mencari k "bebas" merangkumi pokok daripada G berakar pada r, Iaitu, k merentangi pokok sedemikian rupa sehingga, untuk sebarang bucu v, yang k laluan yang menghubungkan r and v dalam k pokok-pokok secara dalaman terputus-putus G. Dalam makalah ini kami memberikan algoritma masa linear untuk dicari k pokok merentang bebas dalam a k-graf satah maksimum yang disambungkan berakar pada mana-mana bucu yang ditetapkan.
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
Sayaka NAGAI, Shin-ichi NAKANO, "A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 5, pp. 1102-1109, May 2001, doi: .
Abstract: Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_5_1102/_p
Salinan
@ARTICLE{e84-a_5_1102,
author={Sayaka NAGAI, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs},
year={2001},
volume={E84-A},
number={5},
pages={1102-1109},
abstract={Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.},
keywords={},
doi={},
ISSN={},
month={May},}
Salinan
TY - JOUR
TI - A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1102
EP - 1109
AU - Sayaka NAGAI
AU - Shin-ichi NAKANO
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2001
AB - Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.
ER -