https://scholars.lib.ntu.edu.tw/handle/123456789/488250
標題: | On the Complexity of the k-Chain Subgraph Cover Problem. | 作者: | Yu, Chang-Wu GEN-HUEY CHEN Ma, Tze-Heng |
關鍵字: | Bipartite graph; Comparability graph; Convex bipartite graph; NC class; P class; Parallel random access machine | 公開日期: | 1998 | 卷: | 205 | 期: | 1-2 | 起(迄)頁: | 85-98 | 來源出版物: | Theor. Comput. Sci. | 摘要: | The k-chain subgraph cover problem asks if the edge set of a given bipartite graph G is the union of the edge sets of k chain graphs, where each chain graph is a subgraph of G. Although the k-chain subgraph cover problem is known to be NP-complete for the class of bipartite graphs, it is still unknown whether this problem is NP-complete or polynomial-time solvable for subclasses of bipartite graphs. In this paper, we answer this question partially by showing that this problem for an important subclass of bipartite graphs, termed convex bipartite graphs, belongs to not only the class P, but also the class NC. More specifically, we show that the k-chain subgraph cover problem on the convex bipartite graph can be solved in O(m2) time sequentially or O(log2n) time in parallel using O(m3) processors on the CRCW PRAM, where n and m denote the number of vertices and edges, respectively. © 1998 - Elsevier Science B.V. All rights reserved. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0142190382&doi=10.1016%2fs0304-3975%2897%2900036-4&partnerID=40&md5=84e67a19cc86b25571b35501da0959da | DOI: | 10.1016/S0304-3975(97)00036-4 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。