Showing cs.DSShow all
2 papers · 1 filter
cs.DS2020
A (probably) optimal algorithm for Bisection on bounded-treewidth graphs
Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the tot…
cs.DS2019
Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem
Yasuaki Kobayashi, Kensuke Kojima, Norihide Matsubara +2
The Balanced Connected Subgraph problem (BCS) was recently introduced by Bhore et al. (CALDAM 2019). In this problem, we are given a graph whose vertices are colored by red or…