3 papers
cs.DS2026
Vertex Cover Interdiction in Bipartite Graphs
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
In the vertex cover interdiction problem, we are given an undirected graph , two integers and and a vertex subset , and we are asked to find a set $X…
cs.DS2025
Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
The minimum sum coloring problem with bundles was introduced by Darbouy and Friggstad (SWAT 2024) as a common generalization of the minimum coloring problem and the minimum sum col…
cs.DS2024
Loss Minimization for Electrical Flows over Spanning Trees on Grids
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
We study the electrical distribution network reconfiguration problem, defined as follows. We are given an undirected graph with a root vertex, demand at each non-root vertex, and r…