Given a connected undirected weighted graph, we are concerned with problems related to partitioning the graph. First of all we look for the closest disconnected graph (the minimum cut problem), here with respect to the Euclidean norm. We are interested in the case of constrained minimum cut problems, where constraints include cardinality or membership requirements, which leads to NP-hard combinatorial optimization problems. These problems are restated as matrix nearness problems for the weight matrix of the graph. A key element in the solution of these matrix nearness problems is the use of a constrained gradient system of matrix differential equations.
Graph partitioning using matrix differential equations
Andreotti, E.;
2019-01-01
Abstract
Given a connected undirected weighted graph, we are concerned with problems related to partitioning the graph. First of all we look for the closest disconnected graph (the minimum cut problem), here with respect to the Euclidean norm. We are interested in the case of constrained minimum cut problems, where constraints include cardinality or membership requirements, which leads to NP-hard combinatorial optimization problems. These problems are restated as matrix nearness problems for the weight matrix of the graph. A key element in the solution of these matrix nearness problems is the use of a constrained gradient system of matrix differential equations.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
