EVA STAR Trefferanzeige

Volltext Volltext.pdf1.pdf (2,1 MB)
URN (für Zitat) http://nbn-resolving.org/urn:nbn:de:swb:90-35182
Titel Engineering planar separator algorithms
Autor Holzer, Martin
Prasinos, Grigorios
Schulz, Frank
Wagner, Dorothea
Zaroliagis, Christos
Institution Fakultät für Informatik (INFORMATIK)
Institut für Logik, Komplexität und Deduktionssysteme (ILKD)
Dokumenttyp Buch
Verlag Karlsruhe
Jahr 2005
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2005,20
ISSN: 1432-7864
We consider classical linear-time planar separator
algorithms, determining for a given planar graph a
small subset of the nodes whose removal separates the
graph into two components of similar size. These algorithms
are based upon Planar Separator Theorems, which
guarantee separators of size asymptotically in the
square root of the number of nodes n and remaining
components of size less than 2n/3. In this work, we
present a comprehensive experimental study of the
algorithms applied to a large variety of graphs, where
the main goal is to find separators that do not only
satisfy upper bounds but also possess other desirable
qualities with respect to separator size and component
balance. We propose the usage of fundamental cycles,
whose size is at most twice the diameter of the graph, as planar
separators: For graphs of small diameter the
guaranteed bound is better than the bounds of the classical
algorithms, and it turns out that this simple strategy almost
always outperforms the other algorithms, even for graphs with
large diameter.