Name
Title | ||
|---|---|---|
A Linear-Time Algorithm to Find Four Independent Spanning Trees in Four-Connected Planar Graphs |
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 four independent spanning trees in a 4-connected planar graph rooted
at any vertex.
|
Year | Venue | Keywords |
|---|---|---|
1999 | International Journal of Foundations of Computer Science | four-connected planar graphs,linear-time algorithm,independent spanning trees,spanning tree,planar graph |
DocType | Volume | Issue |
Journal | 10 | 2 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-65195-0 | 8 |
PageRank | References | Authors |
0.67 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuyuki Miura | 1 | 84 | 8.66 |
| Daishiro Takahashi | 2 | 8 | 0.67 |
| Shin-Ichi Nakano | 3 | 8 | 0.67 |
| Takao Nishizeki | 4 | 1771 | 267.08 |