Algorithms for graph partitioning problems by means of eigenspace relaxations
type: Item
instance of: scholarly article
title: Algorithms for graph partitioning problems by means of eigenspace relaxations
zbMATH Open document ID: 0947.05072
DOI: 10.1016/S0377-2217(99)00060-0
author: Chih-Chien Tu
author: Ce-Kuen Shieh
author: Hsuanjen Cheng
published in: European Journal of Operational Research
publication date: 2000-08-30T00:00:00Z
review text: The authors investigate the problem of partitioning an edge weighted graph into \(k\) connected components so as to minimize the weight of the edges between components. They propose an algorithm for the problem based on eigenvalue methods. The connection between this problem and semi-definite optimization and eigenvalue bounds is well known and therefore the performance of algorithms based on such bounds is of current interest. This paper uses the Donath-Hoffman bound (which is computed by a subgradient algorithm) and a variant of an algorithm by Boppana. Computational results are provided.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 1498195
zbMATH Keywords: graph partitioning
zbMATH Keywords: eigenvalues
zbMATH Keywords: \(k\)-cut
reviewed by: Rakesh V. Vohra
MaRDI profile type: Publication
cites work: An Algorithm for Partitioning the Nodes of a Graph
cites work: Q3338296
cites work: A New Heuristic for Partitioning the Nodes of a Graph
cites work: Q4127646
cites work: Lower Bounds for the Partitioning of Graphs
cites work: A computational study of graph partitioning
cites work: Some simplified NP-complete graph problems
cites work: Q3359644
cites work: A parallel algorithm for bisection width in trees
cites work: A New Lower Bound Via Projection for the Quadratic Assignment Problem
cites work: The variation of the spectrum of a normal matrix
cites work: An Efficient Heuristic Procedure for Partitioning Graphs
cites work: Q3997942
cites work: Q5331504
cites work: Q3138918
cites work: A projection technique for partitioning the nodes of a graph
cites work: Spectral methods for graph bisection problems.
full work available at URL: s0377-2217(99)00060-0
OpenAlex ID: W2022619737
description: scientific article; zbMATH DE number 1498195