節点数ごとに点対互換性グラフを全て求める線形計画を用いた方法
Enumerating All Pairwise Compatibility Graphs with a Given Number of Vertices Based on Linear Programming

概要

Pairwise compatibility graphs (PCGs) are widely used in the field of bioinformatics to study the evolutionary theory. In this paper, we propose an efficient technique for the enumeration of all PCGs with a given number of vertices. For a graph G with n vertices, the proposed method uses a linear program and its duality to get an edge weight assignment of a fixed tree T with n leaves to conclude if G is a PCG or not due to T. We have used our technique on graphs with eight vertices and discovered that there are exactly seven graphs on eight vertices that are non-PCGs (NPCGs), five of which are shown for the first time with this work.

産業界への展開例・適用分野

Pairwise compatibility graphs (PCGs) are widely used in the field of bioinformatics to study the evolutionary theory.

研究者

氏名	専攻	研究室	役職/学年
Azam Naveed Ahmed	数理工学専攻	離散数理分野	博士1回生

---