Efficient matching for column intersection graphs

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

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

To improve the quality and efficiency of hypergraph-based matrix partitioners, we investigate high-quality matchings in column intersection graphs of large sparse binary matrices.We show that such algorithms have a natural decomposition in an integer-weighted graph-matching function and a neighbor-finding function and study the performance of 16 combinations of these functions. We improve upon the original matching algorithm of the Mondriaan matrix partitioner: by using PGA', we improve the averagematching quality from 95.3% to 97.4% of the optimum value; by using our new neighbor-finding heuristic, we obtain comparable quality and speedups of up to a factor of 19.6.

Original languageEnglish
Article number3
JournalJournal of Experimental Algorithmics
Volume19
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • Algorithms
  • Experimentation
  • Performance

Fingerprint

Dive into the research topics of 'Efficient matching for column intersection graphs'. Together they form a unique fingerprint.

Cite this