7 papers · 1 filter
A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
Philip Cervenjak, Junhao Gan, Naonori Kakimura +2
Connected Submodular Maximization (CSM) is a graph problem with important applications to wireless network deployment, path planning, epidemic outbreaks, and cancer genome studies.…
Polynomial Kernels with Reachability for Weighted -Matroid Intersection
Chien-Chung Huang, Naonori Kakimura, Yusuke Kobayashi +1
This paper studies randomized polynomial kernelization for the weighted -matroid intersection problem. While the problem is known to have a kernel of size wher…
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…
Simultaneous Network Design with Restricted Link Usage
Naonori Kakimura, Péter Madarasi, Jannik Matuschke +1
Given a digraph with two terminal vertices and as well as a conservative cost function and several not necessarily disjoint color classes on its arc set, our goal is to fin…
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…
Reconfiguration of labeled matchings in triangular grid graphs
Naonori Kakimura, Yuta Mishima
This paper introduces a new reconfiguration problem of matchings in a triangular grid graph. In this problem, we are given a nearly perfect matching in which each matching edge is…