期刊刊名：科學與工程技術期刊 　 卷期：2卷2期

篇名出版日期：2006年6月1日

作者：YAW-LING LIN,林耀鈴

語言：English

關鍵字：circle trapezoid graphs,circular trapezoid graphs,classification of graphs,independent set,independent dominating set,圓形梯形圖,循環梯形圖,圖形分類問題,最大權重獨立點集合,最小權重獨立控制點集合

被點閱次數：0次

閱讀時間：0sec

摘要：
Along with the direction that generalizes interval graphs and permutation graphs to trapezoid graphs, researchers are now trying to generalize the class known as trapezoid graphs. A circle trapezoid is the region in a circle that lies between two non-crossing chords; thus, circle trapezoid graphs are the intersecting graphs of circle trapezoids within a circle. It should be noted that circle trapezoid graphs properly contain trapezoid graphs, circle graphs and circular-arc graphs as subclasses. Circle trapezoid graphs should not be confused with circular trapezoid graphs. A circular trapezoid is the region within two parallel circles that lies between two non-crossing segments; circular trapezoid graphs are the intersecting graphs of circular trapezoids between two parallel circles. In this paper, the author presents results on two proper super classes of trapezoid graphs, including circle trapezoid graphs and circular trapezoid graphs. It is shown that circle trapezoid graphs and circular trapezoid graphs are two distinct classes of graphs. Furthermore, it is shown that the maximum weighted independent set on circular trapezoid graphs can be found in O(n2loglog n) time; whereas, the minimum weighted independent dominating set of circular trapezoid graphs can be found in O(n2log n) time.

　　　　　[全文下載]