English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the classical minimum and maximum cut problems: find a partitionof vertices of a graph into two disjoint subsets that minimize or maximize thesum of the weights of edges with endpoints in different subsets. It is knownthat if the edge weights are non-negative, then the min-cut problem ispolynomially solvable, while the max-cut problem is NP-hard.  We construct a partition of the positive orthant into convex conescorresponding to the characteristic cut vectors, similar to a normal fan of acut polyhedron. A graph of a cone partition is a graph whose vertices arecones, and two cones are adjacent if and only if they have a common facet. Wedefine adjacency criteria in the graphs of cone partitions for the min-cut andmax-cut problems. Based on them, we show that for both problems the vertexdegrees are exponential, and the graph diameter equals 2. These resultscontrast with the clique numbers of graphs of cone partitions, which are linearfor the minimum cut problem and exponential for the maximum cut problem.

On cone partitions for the min-cut and max-cut problems with non-negative edges