کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427159 686460 2013 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Imbalance is fixed parameter tractable
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Imbalance is fixed parameter tractable
چکیده انگلیسی


• The Imbalance Minimization problem on graphs asks for an ordering of the vertices such that the total imbalance is minimized.
• The problem finds several applications in graph drawing, and is known to be NP-hard.
• In this article, we show that the problem is fixed parameter tractable, when parameterized by the solution size, resolving an open question from the literature.

In the Imbalance Minimization problem we are given a graph G=(V,E)G=(V,E) and an integer b   and asked whether there is an ordering v1…vnv1…vn of V such that the sum of the imbalance of all the vertices is at most b  . The imbalance of a vertex vivi is the absolute value of the difference between the number of neighbors to the left and right of vivi. The problem is also known as the Balanced Vertex Ordering problem and it finds many applications in graph drawing. We show that this problem is fixed parameter tractable and provide an algorithm that runs in time 2O(blogb)⋅nO(1)2O(blogb)⋅nO(1). This resolves an open problem of Kára et al. [On the complexity of the balanced vertex ordering problem, in: COCOON, in: Lecture Notes in Comput. Sci., vol. 3595, 2005, pp. 849–858].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 113, Issues 19–21, September–October 2013, Pages 714–718
نویسندگان
, , ,