کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418638 681701 2010 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On a disparity between relative cliquewidth and relative NLC-width
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On a disparity between relative cliquewidth and relative NLC-width
چکیده انگلیسی

Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by certain terms of operations. Many hard problems on graphs become solvable in polynomial-time if the inputs are restricted to graphs of bounded clique- or NLC-width. Cliquewidth and NLC-width differ at most by a factor of two.The relative counterparts of these parameters are defined to be the minimum number of labels necessary to create a graph while the tree-structure of the term is fixed. We show that Relative Cliquewidth and Relative NLC-width differ significantly in computational complexity. While the former problem is NP-complete the latter is solvable in polynomial time. The relative NLC-width can be computed in O(n3)O(n3) time, which also yields an exact algorithm for computing the NLC-width in time O(3nn)O(3nn). Additionally, our technique enables a combinatorial characterisation of NLC-width that avoids the usual operations on labelled graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 7, 6 April 2010, Pages 828–840
نویسندگان
, ,