On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint
type: Item
instance of: scholarly article
title: On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint
zbMATH Open document ID: 0861.90119
DOI: 10.1007/BF02141748
author: F. Lamour
author: Patrick jun. Ciarlet
published in: Numerical Algorithms
publication date: 1996-10-28T00:00:00Z
review text: The authors present a heuristic which approximates the \(p\)-edge partitioning problem for large sparse graphs with a connectivity constraint on the subsets. It is decomposed into two parts: the computation of an initial partition and an iterative retrofitting process. For the initial step the finiteness and correctness is proven and it is showed by using front-based tools that its complexity grows at most linearly with the number of edges of the graph. For the retrofitting method again based on front techniques a new balancing step has been designed in order to reduce the number of iterations. To illustrate the quality and speed of the heuristic a few examples are given.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 915390
zbMATH Keywords: heuristic
zbMATH Keywords: \(p\)-edge partitioning problem
zbMATH Keywords: large sparse graphs
zbMATH Keywords: connectivity constraint
MaRDI profile type: Publication
cites work: An Algorithm for Partitioning the Nodes of a Graph
cites work: A New Heuristic for Partitioning the Nodes of a Graph
cites work: The Optimal Partitioning of Graphs
cites work: Q5682350
cites work: Graph theory applications
cites work: An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
cites work: An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
cites work: An Efficient Heuristic Procedure for Partitioning Graphs
cites work: A graph partitioning algorithm by node separators
cites work: Q4288580
cites work: Partitioning Sparse Matrices with Eigenvectors of Graphs
cites work: A projection technique for partitioning the nodes of a graph
cites work: Problème de la bipartition minimale d'un graphe
full work available at URL: https://doi.org/10.1007/bf02141748
OpenAlex ID: W2064880188
description: scientific article; zbMATH DE number 915390