Finding the KT Partition of a Weighted Graph in Near-Linear Time.

Simon Apers Pawel Gawrychowski Troy Lee

Published in: APPROX/RANDOM (2022)

Keyphrases

weighted graph
vertex set
shortest path
normalized cut
minimum weight
graph model
graph partitioning
graph structure
spanning tree
min cut
graph laplacian
pairwise similarities
bipartite graph
edge weights
minimum spanning tree
adjacency matrix
worst case
probabilistic model
data objects
data management
maximum weight