A LINEAR-TIME ALGORITHM TO FIND FOUR INDEPENDENT SPANNING TREES IN FOUR CONNECTED PLANAR GRAPHS

DOI10.1142/S0129054199000149zbMath1320.05126MaRDI QIDQ5248999

Daishiro Takahashi, Takao Nishizeki, Kazuyuki Miura, Shin-ichi Nakano

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

graph algorithm; independent spanning tree

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C05: Trees

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Constructing Node-Independent Spanning Trees in Augmented Cubes, Independent spanning trees in crossed cubes, A Simple 2-Approximation for Maximum-Leaf Spanning Tree, Constructing independent spanning trees for locally twisted cubes, Independent spanning trees on even networks, An improved algorithm to construct edge-independent spanning trees in augmented cubes, Linear time algorithms for finding independent spanning trees on pyramid networks, Construction independent spanning trees on locally twisted cubes in parallel

Cites Work

• A linear-time algorithm for four-partitioning four-connected planar graphs
• On independent spanning trees
• Three tree-paths
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs