direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 566-1997

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel
Author
Publication
appeared STACS'98
Classification
not available
Keywords
not available
Abstract
For each minor-closed graph class we show that a simple variant of Boruvka's algorithm computes a MST for any input graph belonging to that class with linear costs. Among minor-closed graph classes are e.g planar graphs, graphs of bounded genus, partial k-trees for fixed k, and linkless or knotless embedable graphs. The algorithm can be implemented on a CRCW PRAM to run in logarithmic time with a work load that is linear in the size of the graph. We develop a new technique to find multiple edges in such a graph that might have applications in other parallel reduction algorithms as well.
Source
Download as [ps.gz]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe