We present the Chromatic Persistence Algorithm (CPA), an event–driven method for computing persistent cohomological features of weighted graphs via graphic arrangements, a classical object in computational geometry. We establish rigorous complexity results: CPA is exponential in the worst case, fixed–parameter tractable in treewidth, and nearly linear for common graph families such as trees, cycles, and series–parallel graphs. Finally, we demonstrate its practical applicability through a controlled experiment on molecular-like graph structures.

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

Algorithm for Interpretable Graph Features via Motivic Persistent Cohomology

  • Yoshihiro Maruyama

摘要

We present the Chromatic Persistence Algorithm (CPA), an event–driven method for computing persistent cohomological features of weighted graphs via graphic arrangements, a classical object in computational geometry. We establish rigorous complexity results: CPA is exponential in the worst case, fixed–parameter tractable in treewidth, and nearly linear for common graph families such as trees, cycles, and series–parallel graphs. Finally, we demonstrate its practical applicability through a controlled experiment on molecular-like graph structures.