完整後設資料紀錄
DC 欄位語言
dc.contributor.authorChang, MSen_US
dc.contributor.authorChen, YHen_US
dc.contributor.authorChang, GJen_US
dc.contributor.authorYan, JHen_US
dc.date.accessioned2014-12-08T15:02:38Z-
dc.date.available2014-12-08T15:02:38Z-
dc.date.issued1996-05-20en_US
dc.identifier.issn0166-218Xen_US
dc.identifier.urihttp://dx.doi.org/10.1016/0166-218X(95)00048-Ven_US
dc.identifier.urihttp://hdl.handle.net/11536/1288-
dc.description.abstractSuppose G=(V,E) is a graph in which each maximal clique C-i is associated with an integer r(i), where 0 less than or equal to r(i) less than or equal toC-i. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that D boolean AND C-igreater than or equal to r(i) for every maximal clique C-i of G. The problem includes the clique-transversal problem, the i,1 clique-cover problem, and for perfect graphs, the maximum q-colorable subgraph problems as special cases. This paper gives complexity results for the problem on subclasses of chordal graphs, e.g., strongly chordal graphs, k-trees, split graphs, and undirected path graphs.en_US
dc.language.isoen_USen_US
dc.subjectclique-transversal seten_US
dc.subjectneighborhood numberen_US
dc.subjectdominationen_US
dc.subjectdualen_US
dc.subjectchordal graphen_US
dc.subjectstrongly chordal graphen_US
dc.subjectk-treeen_US
dc.subjectsplit graphen_US
dc.subjectundirected path graphen_US
dc.titleAlgorithmic aspects of the generalized clique-transversal problem on chordal graphsen_US
dc.typeArticleen_US
dc.identifier.doi10.1016/0166-218X(95)00048-Ven_US
dc.identifier.journalDISCRETE APPLIED MATHEMATICSen_US
dc.citation.volume66en_US
dc.citation.issue3en_US
dc.citation.spage189en_US
dc.citation.epage203en_US
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentDepartment of Applied Mathematicsen_US
顯示於類別:期刊論文


文件中的檔案:

  1. A1996UR03300001.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。