0

What is known about the following problem?

Problem: Given an undirected, connected, planar graph $(V,E)$ with positive edge weights $q: E \to \mathbb{R}_0^+$, and given two distinct vertices $s, t \in V$,

\begin{align} \max_{S, T \subset V} & \quad \sum_{ vw \in E\ |\ v \in S\ \wedge\ w \in T} \hspace{-4ex} q(vw) \newline \mathrm{subject\ to} & \quad S \cup T = V \newline & \quad S \cap T = \emptyset \newline & \quad s \in S \newline & \quad t \in T \newline & \quad S\ \mathrm{is\ a\ connected\ set\ of\ nodes\ in}\ (V,E)\newline & \quad T\ \mathrm{is\ a\ connected\ set\ of\ nodes\ in}\ (V,E)\newline \end{align}

flag
Could you precisely state your problem, with a precise formulation? Also some motivation could help getting interest in your question. – BenoĆ®t Kloeckner Dec 4 at 18:39

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.