The Behavior of Clique-Width under Graph Operations and Graph Transformations

详细信息    查看全文

• 作者：Frank Gurski
• 关键词：Clique ; width ; NLC ; width ; Graph operations ; Graph transformations
• 刊名：Theory of Computing Systems
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：60
• 期：2
• 页码：346-376
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1433-0490
• 卷排序：60

文摘

Clique-width is a well-known graph parameter. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded clique-width. The same holds for NLC-width. In this paper we study the behavior of clique-width and NLC-width under various graph operations and graph transformations. We give upper and lower bounds for the clique-width and NLC-width of the modified graphs in terms of the clique-width and NLC-width of the involved graphs.