Recognition of Probe Ptolemaic Graphs
| 详细信息 | 推荐本文 | |
- 作者：Maw-Shang Chang ; Ling-Ju Hung
- 刊名：Lecture Notes in Computer Science
- 出版时间：2011
- 出版年：2011
- 期刊代码：99_0302-9743
- 类别：cp
- 卷：6460
- 期：1
- 页码：286-290
- 数据来源：sp
摘要
Let G\mathcal{G} denote a graph class. An undirected graph G is called a probe G\mathcal{G} graph if one can make G a graph in G\mathcal{G} by adding edges between vertices in some independent set of G. By definition graph class G\mathcal{G} is a subclass of probe G\mathcal{G} graphs. Ptolemaic graphs are chordal and induced gem free. They form a subclass of both chordal graphs and distance-hereditary graphs. Many problems NP-hard on chordal graphs can be solved in polynomial time on ptolemaic graphs. We proposed an O(nm)-time algorithm to recognize probe ptolemaic graphs where n and m are the numbers of vertices and edges of the input graph respectively.