A linear-time algorithm to find independent spanning trees in maximal planar graphs

Authors
Nagai, S Nakano, S
Citation
S. Nagai et S. Nakano, A linear-time algorithm to find independent spanning trees in maximal planar graphs, IEICE T FUN, E84A(5), 2001, pp. 1102-1109
Citations number
21
Categorie Soggetti
Eletrical & Eletronics Engineeing
Journal title
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
ISSN journal
09168508 → ACNP
Volume
E84A
Issue
5
Year of publication
2001
Pages
1102 - 1109
Database
ISI
SICI code
0916-8508(200105)E84A:5<1102:ALATFI>2.0.ZU;2-O
Abstract
Given a graph G: a designated vertex r and a natural number k, we wish to i ind k "independent" spanning trees of G rooted at r, that is, k spanning tr ees such that, for any vertex rr, the k paths connecting r and v in the k t rees are internally disjoint in G. In this paper we give a linear-time algo rithm to find I; independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.