Journal article
A GRAPH BASED DAVIDSON ALGORITHM FOR THE GRAPH PARTITIONING PROBLEM
International journal of foundations of computer science, Vol.10(2), pp.225-246
06/1999
DOI: 10.1142/S0129054199000162
Abstract
The problem of partitioning a graph such that the number of edges incident to vertices in different partitions is minimized, arises in many contexts. Some examples include its recursive application for minimizing fill-in in matrix factorizations and load-balancing for parallel algorithms. Spectral graph partitioning algorithms partition a graph using the eigenvector associated with the second smallest eigenvalue of a matrix called the graph Laplacian. The focus of this paper is the use graph theory to compute this eigenvector more quickly.
Details
- Title: Subtitle
- A GRAPH BASED DAVIDSON ALGORITHM FOR THE GRAPH PARTITIONING PROBLEM
- Creators
- MICHAEL HOLZRICHTER - Sandia National Laboratories, Albuquerque, NM 5800, USASUELY OLIVEIRA - Dept. of Computer Science, The University of Iowa, Iowa City, IA 52242, USA
- Resource Type
- Journal article
- Publication Details
- International journal of foundations of computer science, Vol.10(2), pp.225-246
- DOI
- 10.1142/S0129054199000162
- ISSN
- 0129-0541
- eISSN
- 1793-6373
- Language
- English
- Date published
- 06/1999
- Academic Unit
- Computer Science; Mathematics
- Record Identifier
- 9984002322902771
Metrics
27 Record Views