We resolve in the affirmative a question of Boppana and Bui: whether simulated annealing
can, with high probability and in polynomial time, find the optimal bisection of a random …

We resolve in the affirmative a question of RB Boppana and T. Bui: whether simulated
annealing can with high probability and in polynomial time, find the optimal bisection of a …

We analyze the behavior of hill-climbing algorithms for the minimum bisection problem on
instances drawn from the\planted bisection" random graph model, Gn; p; q, previously …

In the paper, we describe a polynomial time algorithm that, for every input graph, either
outputs the minimum bisection of the graph or halts without output. More importantly, we …

We investigate the statistical properties of cut sizes generated by heuristic algorithms which
solve the graph bisection problem approximately. On an ensemble of sparse random …

We present a novel exact algorithm for the minimum graph bisection problem, whose goal is
to partition a graph into two equally-sized cells while minimizing the number of edges …

The minimum bisection problem is to partition the vertices of a graph into two classes of
equal size so as to minimize the number of crossing edges. Computing a minimum bisection …

We present a novel exact algorithm for the minimum graph bisection problem, whose goal is
to partition a graph into two equally-sized cells while minimizing the number of edges …

The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into
two equal‐sized groups so as to minimize the number of edges that cross the partition. The …

The NP-hard graph bisection problem is to partition the nodes of an undirected graph into
two equal-sized groups so as to minimize the number of edges that cross the partition. The …