Partitioning planar graphs with costs and weights. (English) Zbl 1014.68780
Mount, David M. (ed.) et al., Algorithm engineering and experiments. 4th international workshop, ALENEX 2002, San Francisco, CA, USA, January 4-5, 2002. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2409, 98-110 (2002).
Summary: A graph separator is a set of vertices or edges whose removal divides an input graph into components of bounded size. This paper describes new algorithms for computing separators in planar graphs as well as techniques that can be used to speed up their implementation and improve the partition quality. In particular, we consider planar graphs with costs and weights on the vertices, where weights are used to estimate the sizes of the components and costs are used to estimate the size of the separator. We show that one can find a small separator that divides the graph into components of bounded size. We describe implementations of the partitioning algorithms and discuss results of our experiments.
For the entire collection see [Zbl 1008.68692].
For the entire collection see [Zbl 1008.68692].
MSC:
| 68U99 | Computing methodologies and applications |
| 68W05 | Nonnumerical algorithms |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
