Complexity properties of complementary prisms

详细信息    查看全文

• 作者：Marcio Antônio Duarte ; Lucia Penso…
• 关键词：Complementary prism ; Clique ; Independent set ; k ; Domination ; \(P_3\) ; Convexity
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：33
• 期：2
• 页码：365-372
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

The complementary prism \(G\bar{G}\) of a graph G arises from the disjoint union of the graph G and its complement \(\bar{G}\) by adding the edges of a perfect matching joining pairs of corresponding vertices of G and \(\bar{G}\). Haynes, Henning, Slater, and van der Merwe introduced the complementary prism and as a variation of the well-known prism. We study algorithmic/complexity properties of complementary prisms with respect to cliques, independent sets, k-domination, and especially \(P_3\)-convexity. We establish hardness results and identify some efficiently solvable cases.