3 citations · 12 across the 26 of their papers we have counts for
3 papers · 1 filter
Essentially Tight Kernels for (Weakly) Closed Graphs
Tomohiro Koana, Christian Komusiewicz, Frank Sommer
We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closu…
The Complexity of Gerrymandering Over Graphs: Paths and Trees
Matthias Bentert, Tomohiro Koana, Rolf Niedermeier
Roughly speaking, gerrymandering is the systematic manipulation of the boundaries of electoral districts to make a specific (political) party win as many districts as possible. Whi…
A Refined Complexity Analysis of Fair Districting over Graphs
Niclas Boehmer, Tomohiro Koana, Rolf Niedermeier
We study the NP-hard Fair Connected Districting problem recently proposed by Stoica et al. [AAMAS 2020]: Partition a vertex-colored graph into k connected components (subsequently…