Using domain decomposition to find graph bisectors

DOI10.1007/BF02510238MaRDI QIDQ1371661zbMATH OpenOpenAlexFDO

Authors Cleve Ashcraft, Joseph W. H. Liu

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

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

Cites work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A graph partitioning algorithm by node separators
• An Efficient Heuristic Procedure for Partitioning Graphs
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement
• Compressed Graphs and the Minimum Degree Algorithm
• Computing the block triangular form of a sparse matrix
• Finding good approximate vertex and edge partitions is NP-hard
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 741125 (Why is no real title available?)
• scientific article; zbMATH DE number 741181 (Why is no real title available?)
• Nested Dissection of a Regular Finite Element Mesh
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Robust Ordering of Sparse Matrices using Multisection
• The Evolution of the Minimum Degree Ordering Algorithm

Cited in

(5)

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

Describes a project that uses

Uses Software

• Chaco
• METIS
• symrcm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1371661)