Spectral partitioning with multiple eigenvectors

DOI10.1016/S0166-218X(98)00083-3zbMath0918.68076MaRDI QIDQ1276952

Andrew B. Kahng, Charles J. Alpert, So-Zen Yao

Publication date: 23 August 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph partitioning

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Logic programming (68N17)

Related Items (17)

Face recognition using spectral features ⋮ Almost-invariant sets and invariant manifolds - connecting probabilistic and geometric descriptions of coherent structures in flows ⋮ On the multiplicity of Laplacian eigenvalues and Fiedler partitions ⋮ Online summarization of dynamic graphs using subjective interestingness for sequential data ⋮ Grouping objects in multi-band images using an improved eigenvector-based algorithm ⋮ ILP-Based Local Search for Graph Partitioning ⋮ Community detection in networks via a spectral heuristic based on the clustering coefficient ⋮ Improving graph partitions using submodular functions. ⋮ On the Structure of Isometrically Embeddable Metric Spaces ⋮ A vector partitioning approach to detecting community structure in complex networks ⋮ Worst-case ratios of networks in the rectilinear plane ⋮ Statistically optimal almost-invariant sets ⋮ Spectral methods for graph clustering - a survey ⋮ Robust FEM-Based Extraction of Finite-Time Coherent Sets Using Scattered, Sparse, and Incomplete Trajectories ⋮ Community detection based on network communicability ⋮ Unnamed Item ⋮ Partitions of networks that are robust to vertex permutation dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The indefinite zero-one quadratic problem
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Modeling hypergraphs by graphs with the same mincut properties
• Laplacian eigenvalues and the maximum cut problem
• A computational study of graph partitioning
• Solving the max-cut problem using eigenvalues
• A projection technique for partitioning the nodes of a graph
• Recent directions in netlist partitioning: a survey
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• A New Heuristic for Partitioning the Nodes of a Graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• An Algorithm for Partitioning the Nodes of a Graph
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Equivalence of Memory to “Random Logic”
• An r-Dimensional Quadratic Placement Algorithm
• Lower Bounds for the Partitioning of Graphs

This page was built for publication: Spectral partitioning with multiple eigenvectors