Scholarlink

The use of random graphs for algorithm benchmarking has found considerable use in recent years. The parametric generation of random benchmark graphs has been developed to analyze solution quality for community detection algorithms and for general scalability studies of parallel graph algorithms, among other applications. This paper presents general frameworks for the generation of benchmark graphs for two widely utilized problems within scientific computing applications: distance-1 coloring and maximum matching. We present methods to systematically generate useful instances of benchmarks for these problems, prove their ground truth solutions to be correct, and demonstrate their usage on real algorithm implementations in an experimental study.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Scalable Benchmark Graph Generation for the Maximum Cardinality Matching and Distance-1 Minimum Coloring Problems

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Anthony Fabius,
  • Ujwal Pandey,
  • Dong Lin,
  • Yash Kaul,
  • George M. Slota

摘要

The use of random graphs for algorithm benchmarking has found considerable use in recent years. The parametric generation of random benchmark graphs has been developed to analyze solution quality for community detection algorithms and for general scalability studies of parallel graph algorithms, among other applications. This paper presents general frameworks for the generation of benchmark graphs for two widely utilized problems within scientific computing applications: distance-1 coloring and maximum matching. We present methods to systematically generate useful instances of benchmarks for these problems, prove their ground truth solutions to be correct, and demonstrate their usage on real algorithm implementations in an experimental study.