Quality matching and local improvement for multilevel graph-partitioning

DOI10.1016/S0167-8191(00)00049-1MaRDI QIDQ1583343zbMATH OpenOpenAlexWikidataFDO

Authors Burkhard Monien, Robert Preis, Ralf Diekmann

Publication date 26 October 2000

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-8191(00)00049-1

zbMATH Keywords

multilevelmatchinglocal improvementbisection-widthgraph-partitioning

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Engineering multilevel graph partitioning algorithms
• \(n\)-level graph partitioning
• scientific article; zbMATH DE number 1942408
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A partitioning requiring rapidity and quality: the multilevel method and partitions refinement algorithms

Cited in

(12)

• Weighted matching in the semi-streaming model
• Local expansion concepts for detecting transport barriers in dynamical systems
• Engineering multilevel graph partitioning algorithms
• TRANSPORT IN DYNAMICAL ASTRONOMY AND MULTIBODY PROBLEMS
• Tree-based coarsening and partitioning of complex networks
• A simple approximation algorithm for the weighted matching problem
• New methods in celestial mechanics and mission design
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• \(n\)-level graph partitioning
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• Upper bounds on the bisection width of 3- and 4-regular graphs
• Efficient matching for column intersection graphs

Describes a project that uses

Uses Software

• TOP/DOMDEC
• PARTY
• Chaco
• Scotch

This page was built for publication: Quality matching and local improvement for multilevel graph-partitioning

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