We give a randomized algorithm for Directed Hamiltonian Cycle on $n$-vertex directed graphs that runs in time $O^*((375/196)^n)=O^*(1.9133^n)$. For general directed graphs, this is the first improvement in the exponential base over the classical $O^*(2^n)$-time algorithms of Bellman and Held--Karp (1962). To obtain thi...
A randomized algorithm returns a $(1\pm\varepsilon)-approximation with failure probability at most $\delta$ in $O^*(2^k\varepsilon^{-2}\log(1/\delta)$ time.
The SCA problem can be solved in time and admits a polynomial kernel with vertices and bits and the algorithms are based on a particularly simple reduction to Strongly Connected Spanning Subgraph with two edge costs.
We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its ori...
Tomohiro Koana, Y. Oh, Hirotaka Yoneda· 0 citations
We study restricted-link augmentation to $2$-vertex-connectivity. An instance consists of a graph $G$, possibly disconnected, a set $L$ of admissible links on its vertices, integer link costs in $\{1,\dots,W\}$, and an integer $k$; the task is to add at most $k$ links of minimum total cost so that the resulting multigr...
The results reveal that, in this setting, MCIS is strictly harder than ISI, and it is shown that it becomes NP-hard already when each input graph has cluster vertex deletion number 2.
Tomohiro Koana, Soh Kumabe, Y. Otachi· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
