solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3686次
Graph partitioning using matrix differential equations. (arXiv:1712.05993v1 [math.NA])
来源于:arXiv
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. Furthermore, we are
interested in ambiguity issues, that is in the robustness of clustering
algorithms that are based on Fiedler spectral partitioning. The above-mentioned
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. 查看全文>>