A linear time algorithm for graph partition problems
type: Item
instance of: scholarly article
title: A linear time algorithm for graph partition problems
zbMATH Open document ID: 0765.68045
DOI: 10.1016/0020-0190(92)90126-G
published in: Information Processing Letters
publication date: 1993-01-16T00:00:00Z
review text: We present an \(O(| V|+| E|)\) time algorithm which partitions the set of vertices of an undirected graph \(G=\langle V,E\rangle\) with maximum degree \(\Delta\) and minimum degree \(\delta\) to \(\{A,\bar A\}\) such that the following hold: (i) The number of edges with one end point in \(A\) and the other end point in \(\bar A\) is at least \(| E|/2\). (ii) The difference between the number of vertices in \(A\) and the number of vertices in \(\bar A\) is 0 if \(| V|\) is even, and is 1 if \(| V|\) is odd. (iii) The absolute value of the difference between the number of edges with both end points in \(A\) and the number of edges with both end points in \(\bar A\) is at most \((\Delta-\delta)/2\) if \(| V|\) is even, and is at most \((\Delta+1)/2\) if \(| V|\) is odd. The partitioning algorithms for which (i) and (ii) hold are known, see \textit{M. K. Goldberg} and \textit{R. Gardner} [Progress in graph theory, Proc. Conf. Combinatorics, Waterloo/Ont. 1982, 295-305 (1984; Zbl 0559.05059)]. However, we are not aware of any algorithm for which (i), (ii), and (iii) simultaneously hold. Section 2 contains our main results. We describe our algorithm which has running time \(O(| V|+| E|)\) and \(O(| V|^ 2)\), for unweighted graphs and weighted graphs, respectively. Our algorithm is a modified version of the algorithm of \textit{C. H. Papadimitriou} and \textit{M. Yannakakis} [(*) Optimization, approximation, and complexity class, Proc. 20th ACM Symp. Theory Comp., 229-234 (1988)] for approximating the maximum cut problem. We remark that for the cut generated by the algorithm in (*) property (i) holds, but properties (ii) or (iii) may not hold. In Section 3 we describe the applications of our algorithm to three NP- hard problems: the maximum cut problem, the graph bisection problem, and the bottleneck bipartite number problem.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 92086
zbMATH Keywords: linear time algorithm
zbMATH Keywords: graph partition
zbMATH Keywords: partitioning algorithms
zbMATH Keywords: maximum cut problem
zbMATH Keywords: graph bisection problem
zbMATH Keywords: bottleneck bipartite number problem
author: Lane Clark
author: Farhad Shahrokhi
author: László A. Székely
MaRDI profile type: Publication
cites work: Q3682518
cites work: Q3818315
cites work: Some simplified NP-complete graph problems
cites work: Q3347934
cites work: Sparsest cuts and bottlenecks in graphs
cites work: Q4739657
cites work: The maximum concurrent flow problem
cites work: Q3707420
full work available at URL: 0020-0190(92)90126-g
OpenAlex ID: W1991957444
Recommended article: An exact algorithm for graph partitioning
Recommended article: Approximation Algorithms for Some Graph Partitioning Problems
Recommended article: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Recommended article: Q3717092
Recommended article: Graph partitioning using linear and semidefinite programming
Recommended article: Q3835330
Recommended article: Partitioning into degenerate graphs in linear time
Recommended article: Parameterized algorithms for graph partitioning problems
Recommended article: Q4526868
description: scientific article; zbMATH DE number 92086