کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429923 687723 2007 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Online promise problems with online width metrics
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Online promise problems with online width metrics
چکیده انگلیسی

In this article we consider the application of ideas from parameterized complexity, and topological graph theory, to online problems. We focus on parameterized promise problems, where we are promised that the problem input obeys certain properties, or is presented in a certain fashion.We explore the effects of using graph width metrics as restrictions on the input to online problems. It seems natural to suppose that, for graphs having some form of bounded width, good online algorithms may exist for a number of natural problems. In the work presented we concentrate on online graph coloring problems, where we restrict the allowed input to instances having some form of bounded treewidth or pathwidth.We also consider the effects of restricting the presentation of the input to some form of bounded width decomposition or layout. A consequence of this part of the work is the clarification of a new parameter for graphs, persistence, which arises naturally in the online setting, and is of interest in its own right. We present some basic results regarding the general recognition of graphs having bounded persistence path decompositions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 73, Issue 1, February 2007, Pages 57-72