Bin packing asks whether a collection of items can be packed into at most a given number of bins of a given capacity. We consider the high-multiplicity setting with $d$ distinct item sizes, in which both the item sizes and the number of items of each size are encoded in binary. Goemans and Rothvos (JACM 2020) gave an X...
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
The problem is reduced to a boundary-pair variant of $2-vertex-connected spanning subgraph, where each vertex is assigned a pair of incident edges with an associated pair cost, and a deterministic algorithm is given with running time $O^*(36^kW)$.
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.
