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
Étant donné un graphique G, un sommet désigné r et un nombre naturel k, nous souhaitons trouver k arbres couvrants "indépendants" de G enraciné à r, Qui est, k s'étendant sur des arbres tels que, pour tout sommet v, k chemins reliant r et à la v dans le k les arbres sont intérieurement disjoints dans G. Dans cet article, nous donnons un algorithme en temps linéaire pour trouver k arbres couvrants indépendants dans un k-graphe planaire maximal connecté enraciné à n'importe quel sommet désigné.
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.
Copier
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
Copier
@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},}
Copier
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 -