Scholarlink

<p>In this paper, we study the ratio between the maximum weight perfect matching and the maximum weight matching. We show that for n-prism graphs this ratio is 1/2, when n is odd and ≤2/3 otherwise. This work is inspired by the use of triangle meshes to model solid objects especially in the conversion of these meshes into quadrangulated meshes.</p>

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

The Cost of Perfect Matchings in Prism Graphs

  • 期刊论文

  • 发表日期：

    2026年1月29日

查看全文
  • Ingrid Borchert,
  • Diana Sasaki,
  • Diego Nicodemos

摘要

In this paper, we study the ratio between the maximum weight perfect matching and the maximum weight matching. We show that for n-prism graphs this ratio is 1/2, when n is odd and ≤2/3 otherwise. This work is inspired by the use of triangle meshes to model solid objects especially in the conversion of these meshes into quadrangulated meshes.