A novel algorithmic approach is presented for the problem of partitioning a connected undirected weighted graph under constraints such as cardinality or membership requirements or must-link and cannot-link constraints. Such constrained problems can be NP-hard combinatorial optimization problems. They are restated as matrix nearness problems for the weight matrix of the graph, where the objective is to minimize the distance between the given weight matrix and perturbed weight matrices for which a functional of an eigenvalue and eigenvector of the graph Laplacian takes its minimal value. A key element in the numerical solution of these matrix nearness problems is the use of a gradient system of matrix differential equations for the functional.

Constrained graph partitioning via matrix differential equations

Andreotti E.;Guglielmi N.;
2019-01-01

Abstract

A novel algorithmic approach is presented for the problem of partitioning a connected undirected weighted graph under constraints such as cardinality or membership requirements or must-link and cannot-link constraints. Such constrained problems can be NP-hard combinatorial optimization problems. They are restated as matrix nearness problems for the weight matrix of the graph, where the objective is to minimize the distance between the given weight matrix and perturbed weight matrices for which a functional of an eigenvalue and eigenvector of the graph Laplacian takes its minimal value. A key element in the numerical solution of these matrix nearness problems is the use of a gradient system of matrix differential equations for the functional.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/145778
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact