Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement

DOI10.1137/S0895479896308433zbMath0907.68138OpenAlexW2049638680MaRDI QIDQ4389077

Joseph W. H. Liu, Cleve Ashcraft

Publication date: 11 May 1998

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895479896308433

zbMATH Keywords

graph bisectionnetwork flownested dissectionmultisectionDulmage-Mendelsohn decompositionordering algorithms

Mathematics Subject Classification ID

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

Related Items (4)

Using domain decomposition to find graph bisectors ⋮ On sparse matrix orderings in interior point methods ⋮ 1.5D Parallel Sparse Matrix-Vector Multiply ⋮ A survey of direct methods for sparse linear systems

Uses Software

• Chaco

This page was built for publication: Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement