On the Optimality of the Median Cut Spectral Bisection Graph Partitioning Method

DOI10.1137/S1064827594262649zbMath0872.65056WikidataQ57397390 ScholiaQ57397390MaRDI QIDQ4340830

W. K. Szeto, Tony F. Chan, Patrick~jun. Ciarlet

Publication date: 12 June 1997

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

zbMATH Keywords

parallel computinggraph partitioningFiedler vectorgraph Laplacianrecursive spectral bisectionminimum cut graph bisectionsecond eigenvector of the Laplacian

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05)

Related Items

On the maximal error of spectral approximation of graph bisection ⋮ A literature survey of matrix methods for data science ⋮ Nodal decompositions of graphs ⋮ Algebraic connectivity and disjoint vertex subsets of graphs ⋮ An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification ⋮ Spectral bisection of graphs and connectedness ⋮ A divisive spectral method for network community detection