Kernels in planar digraphs

A set $S$ of vertices in a digraph $D=(V,A)$ is a kernel if $S$ is independent and every vertex in $V-S$ has an out-neighbour in $S$. We show that there exists an $O(3^{\delta \sqrt{k}} n)$~% \footnote{Throughout this paper the constants $\delta$ and $c$ are the same as the comparative constants mentioned in~\cite{kn:alber}.} algorithm to check … Read more

Upper Bounds on ATSP Neighborhood Size

We consider the Asymmetric Traveling Salesman Problem (ATSP) and use the definition of neighborhood by Deineko and Woeginger (see Math. Programming 87 (2000) 519-542). Let $\mu(n)$ be the maximum cardinality of polynomial time searchable neighborhood for the ATSP on $n$ vertices. Deineko and Woeginger conjectured that $\mu (n)< \beta (n-1)!$ for any constant $\beta >0$ … Read more