TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1997

COGA 5-Wheel


zur Navigation

Preprints 1997

Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel
Zitatschlüssel Report-566-1997
Autor Gustedt, Jens
Jahr 1997
Nummer 566
Notiz appeared STACS'98
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe