Efficient matching for column intersection graphs

DOI10.1145/2616587MaRDI QIDQ2828179zbMATH OpenOpenAlexWikidataFDO

Authors B. O. Fagginger Auer, R. H. Bisseling

Publication date 24 October 2016

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/307294

zbMATH Keywords

column intersection graphsheuristic algorithmsweighted graph matching

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Nonnumerical algorithms (68W05)

Recommendations

• A Matrix Partitioning Interface to PaToH in MATLAB
• Quality matching and local improvement for multilevel graph-partitioning
• Abusing a hypergraph partitioner for unweighted graph partitioning
• On two-dimensional sparse matrix partitioning: models, methods, and a recipe
• Multilevel algorithm for graph partitioning

Cites work

• A simple approximation algorithm for the weighted matching problem
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication
• An Efficient Heuristic Procedure for Partitioning Graphs
• Engineering Algorithms for Approximate Weighted Matching
• Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems
• Faster scaling algorithms for general graph matching problems
• scientific article; zbMATH DE number 1304326 (Why is no real title available?)
• scientific article; zbMATH DE number 1982180 (Why is no real title available?)
• scientific article; zbMATH DE number 2116061 (Why is no real title available?)
• Improved linear time approximation algorithms for weighted matchings
• Maximum matching and a polyhedron with 0,1-vertices
• Paths, Trees, and Flowers
• The University of Florida sparse matrix collection
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives

Cited in

(2)

• An efficient method to evaluate intersections on big data sets
• A Matrix Partitioning Interface to PaToH in MATLAB

Describes a project that uses

Uses Software

• SparseMatrix
• LEMON
• Zoltan
• PaToH
• BSPedupack

This page was built for publication: Efficient matching for column intersection graphs

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