Using domain decomposition to find graph bisectors

DOI10.1007/BF02510238zbMath1043.65509OpenAlexW2086609738MaRDI QIDQ1371661

Joseph W. H. Liu, Cleve Ashcraft

Publication date: 2 February 1998

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02510238

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Graph theory (including graph drawing) in computer science (68R10) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (5)

On sparse matrix orderings in interior point methods ⋮ A survey of direct methods for sparse linear systems ⋮ Spectral bounds for the maximum cut problem ⋮ From Graph Orientation to the Unweighted Maximum Cut ⋮ Speeding up a memetic algorithm for the max-bisection problem

Uses Software

• METIS
• symrcm
• Chaco

Cites Work

• Finding good approximate vertex and edge partitions is NP-hard
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• The Evolution of the Minimum Degree Ordering Algorithm
• An Efficient Heuristic Procedure for Partitioning Graphs
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A graph partitioning algorithm by node separators
• Computing the block triangular form of a sparse matrix
• Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement
• Robust Ordering of Sparse Matrices using Multisection
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Compressed Graphs and the Minimum Degree Algorithm
• Nested Dissection of a Regular Finite Element Mesh
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Using domain decomposition to find graph bisectors