Full metadata record
DC FieldValueLanguage
dc.contributor.authorGuruswami, Ven_US
dc.contributor.authorRangan, CPen_US
dc.contributor.authorChang, MSen_US
dc.contributor.authorChang, GJen_US
dc.contributor.authorWong, CKen_US
dc.date.accessioned2014-12-08T15:01:11Z-
dc.date.available2014-12-08T15:01:11Z-
dc.date.issued1998en_US
dc.identifier.isbn3-540-65195-0en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/11536/87-
dc.description.abstractThe vertex-disjoint triangles (VDT) problem asks for a set of maximum number of pairwise vertex-disjoint triangles in a given graph G. The triangle cover problem asks for the existence of a perfect triangle packing in a graph G. It is known that the triangle cover problem is NP-complete on general graphs with clique number 3 [6]. The VDT problem is MAX SNP-hard on graphs with maximum degree four, while it can be approximated within 3/2 + epsilon, for any epsilon > 0, in polynomial time [11]. We prove that the VDT problem is NP-complete even when the input graphs are chordal, planar, line or total graphs. We present an O(m root n) algorithm for the VDT problem on split graphs and an O(n(3)) algorithm for the VDT problem on cographs. A linear algorithm for the triangle cover problem on strongly chordal graphs is also presented. Finally, the notion of packing-hardness, which may be crucial to the understanding of the difficulty of generalized matching problems, is defined.en_US
dc.language.isoen_USen_US
dc.titleThe vertex-disjoint triangles problemen_US
dc.typeArticle; Proceedings Paperen_US
dc.identifier.journalGRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCEen_US
dc.citation.volume1517en_US
dc.citation.spage26en_US
dc.citation.epage37en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000083174200003-
Appears in Collections:Conferences Paper