Alexander Nover

most citedCut Polytopes of Minor-free Graphs

2 citations · 2 across the 1 of their papers we have counts for

collaborators

3 papers

math.CO2020

On the Bond Polytope

Markus Chimani, Martina Juhnke-Kubitzke, Alexander Nover

Given a graph $G = (V, E)$ , the maximum bond problem searches for a maximum cut $δ (S) \subseteq E$ with $S \subseteq V$ such that $G [S]$ and $G [V ∖ S]$ are connected. This prob…

math.CO2019★ 2 cited

Cut Polytopes of Minor-free Graphs

Markus Chimani, Martina Juhnke-Kubitzke, Alexander Nover +1

The cut polytope of a graph $G$ is the convex hull of the indicator vectors of all cuts in $G$ and is closely related to the MaxCut problem. We give the facet-description of cut po…

cs.DS2019

Maximum Cut Parameterized by Crossing Number

Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke +3

Given an edge-weighted graph $G$ on $n$ nodes, the NP-hard Max-Cut problem asks for a node bipartition such that the sum of edge weights joining the different partitions is maximiz…