Bruce Reed ; David R. Wood
-
Fast separation in a graph with an excluded minor
dmtcs:3419 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3419
Fast separation in a graph with an excluded minor
Authors: Bruce Reed ; David R. Wood 1
NULL##NULL
Bruce Reed;David R. Wood
1 Departament de Matemàtica Aplicada II
Let $G$ be an $n$-vertex $m$-edge graph with weighted vertices. A pair of vertex sets $A,B \subseteq V(G)$ is a $\frac{2}{3} - \textit{separation}$ of $\textit{order}$ $|A \cap B|$ if $A \cup B = V(G)$, there is no edge between $A \backslash B$ and $B \backslash A$, and both $A \backslash B$ and $B \backslash A$ have weight at most $\frac{2}{3}$ the total weight of $G$. Let $\ell \in \mathbb{Z}^+$ be fixed. Alon, Seymour and Thomas [$\textit{J. Amer. Math. Soc.}$ 1990] presented an algorithm that in $\mathcal{O}(n^{1/2}m)$ time, either outputs a $K_\ell$-minor of $G$, or a separation of $G$ of order $\mathcal{O}(n^{1/2})$. Whether there is a $\mathcal{O}(n+m)$ time algorithm for this theorem was left as open problem. In this paper, we obtain a $\mathcal{O}(n+m)$ time algorithm at the expense of $\mathcal{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 $\epsilon \in [0,\frac{1}{2}]$, our algorithm either outputs a $K_\ell$-minor of $G$, or a separation of $G$ with order $\mathcal{O}(n^{(2-\epsilon )/3})$ in $\mathcal{O}(n^{1+\epsilon} +m)$ time.
Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
3 Documents citing this article
Source : OpenCitations
Reed, Bruce; Li, Zhentao, Optimization And Recognition For K 5-Minor Free Graphs In Linear Time, Lecture Notes In Computer Science, pp. 206-215, 10.1007/978-3-540-78773-0_18.
Tazari, Siamak; MĂźller-Hannemann, Matthias, 2008, A Faster Shortest-Paths Algorithm For Minor-Closed Graph Classes, Graph-Theoretic Concepts In Computer Science, pp. 360-371, 10.1007/978-3-540-92248-3_32.
Yuster, Raphael, 2010, Single Source Shortest Paths In H-minor Free Graphs, Theoretical Computer Science, 411, 34-36, pp. 3042-3047, 10.1016/j.tcs.2010.04.028.