Partitioning planar graphs with vertex costs: Algorithms and applications

Authors
Citation
Hn. Djidjev, Partitioning planar graphs with vertex costs: Algorithms and applications, ALGORITHMIC, 28(1), 2000, pp. 51-75
Citations number
29
Categorie Soggetti
Engineering Mathematics
Journal title
ALGORITHMICA
ISSN journal
01784617 → ACNP
Volume
28
Issue
1
Year of publication
2000
Pages
51 - 75
Database
ISI
SICI code
0178-4617(200009)28:1<51:PPGWVC>2.0.ZU;2-K
Abstract
We prove separator theorems in which the size of the separator is minimized with respect to non-negative vertex costs. We show that for any planar gra ph G there exists a vertex separator of total sum of vertex costs at most c root Sigma(nu is an element of V(G))(cost(nu))(2) and that this bound is o ptimal to within a constant factor. Moreover, such a separator can be found in linear time. This theorem implies a variety of other separation results . We describe applications of our separator theorems to graph embedding pro blems, to graph pebbling, and to multicommodity flow problems.