題名: | Probe Bipartite Distance-Hereditary Graphs |
作者: | Chang, Maw-Shang Jr Hung, Ling-Ju Jr Rossmanith, Peter Jr |
期刊名/會議名稱: | NCS 2009 |
摘要: | A graph G = (V,E) is called a probe graph of graph class G if V can be partitioned into two sets P (probes) and N (nonprobes),where N is an independent set, such that G can be embedded into a graph of G by adding edges between certain nonprobes. A graph is distance hereditary if the distance between any two vertices remains the same in every connected induced subgraph. Bipartite distance-hereditary graphs are both bipartite and distance hereditary. In this paper we give an O(nm)-time algorithm for recognizing probe graphs of bipartite distance-hereditary graphs. |
日期: | 2011-02-21T23:27:18Z |
分類: | 2009年 NCS 全國計算機會議 |
文件中的檔案:
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
AB 1-3.pdf | 164.3 kB | Adobe PDF | 檢視/開啟 |
在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。