NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph
This paper investigates the computational complexity of deciding whether the vertices of a graph can be partitioned into a disjoint union of cliques and a triangle-free subgraph. This problem is known to be NP-complete on arbitrary graphs. We show that this problem remains NP-complete even when rest...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| التنسيق: | article |
| منشور في: |
2014
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/7595 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://pdfs.semanticscholar.org/be27/7d8d21b644a768c443fe5553033ef879623f.pdf |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513482424057856 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Feghali, Carl Muller, Haiko |
| author2_role | author author |
| author_facet | Abu-Khzam, Faisal N. Feghali, Carl Muller, Haiko |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Feghali, Carl Muller, Haiko |
| dc.date.none.fl_str_mv | 2014 2018-04-26T06:44:19Z 2018-04-26T06:44:19Z 2018-04-26 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7595 Feghali, C., Abu-Khzam, F. N., & Müller, H. (2014). NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph. arXiv preprint arXiv:1403.5248. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://pdfs.semanticscholar.org/be27/7d8d21b644a768c443fe5553033ef879623f.pdf |
| dc.language.none.fl_str_mv | en |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | This paper investigates the computational complexity of deciding whether the vertices of a graph can be partitioned into a disjoint union of cliques and a triangle-free subgraph. This problem is known to be NP-complete on arbitrary graphs. We show that this problem remains NP-complete even when restricted to planar graphs and perfect graphs. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_15af15bbc98cedbc7e7283d37d3bd79a |
| identifier_str_mv | Feghali, C., Abu-Khzam, F. N., & Müller, H. (2014). NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph. arXiv preprint arXiv:1403.5248. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/7595 |
| publishDate | 2014 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraphAbu-Khzam, Faisal N.Feghali, CarlMuller, HaikoThis paper investigates the computational complexity of deciding whether the vertices of a graph can be partitioned into a disjoint union of cliques and a triangle-free subgraph. This problem is known to be NP-complete on arbitrary graphs. We show that this problem remains NP-complete even when restricted to planar graphs and perfect graphs.Pre-printN/A2018-04-26T06:44:19Z2018-04-26T06:44:19Z20142018-04-26Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/articlehttp://hdl.handle.net/10725/7595Feghali, C., Abu-Khzam, F. N., & Müller, H. (2014). NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph. arXiv preprint arXiv:1403.5248.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://pdfs.semanticscholar.org/be27/7d8d21b644a768c443fe5553033ef879623f.pdfeninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/75952021-03-19T10:43:13Z |
| spellingShingle | NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph |
| title_full | NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph |
| title_fullStr | NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph |
| title_full_unstemmed | NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph |
| title_short | NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph |
| title_sort | NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph |
| url | http://hdl.handle.net/10725/7595 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://pdfs.semanticscholar.org/be27/7d8d21b644a768c443fe5553033ef879623f.pdf |