## DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:
DMTCS Conference vol AE (2005), pp. 45-50

## 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

### DMTCS Conference Volume AE (2005), pp. 45-50

author: Bruce Reed and David R. Wood Fast separation in a graph with an excluded minor graph algorithm, separator, minor Let G be an n -vertex m -edge graph with weighted vertices. A pair of vertex sets A,B⊆V(G) is a 2/3-separation of order |A∩B| if A ∪B = V(G) , there is no edge between A \ B and B \ A , and both A \ B and B \ A have weight at most 2/3 the total weight of G . Let ℓ∈ℤ+ be fixed. Alon, Seymour and Thomas [J. Amer. Math. Soc. 1990] presented an algorithm that in O (n 1/2 m) time, either outputs a K ℓ -minor of G , or a separation of G of order O (n 1/2 ) . Whether there is a O (n+m) time algorithm for this theorem was left as open problem. In this paper, we obtain a O (n+m) time algorithm at the expense of O (n 2/3 ) separator. Moreover, our algorithm exhibits a tradeoff between running time and the order of the separator. In particular, for any given ε∈[0,1/2] , our algorithm either outputs a K ℓ -minor of G , or a separation of G with order O (n (2-ε)/3 ) in O (n 1+ε +m) time. If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. Bruce Reed and David R. Wood (2005), Fast separation in a graph with an excluded minor , in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), Stefan Felsner (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AE, pp. 45-50 For a corresponding BibTeX entry, please consider our BibTeX-file. dmAE0110.ps.gz (72 K) dmAE0110.ps (176 K) dmAE0110.pdf (179 K)