کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141800 957092 2006 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Exact algorithms for a discrete metric labeling problem
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Exact algorithms for a discrete metric labeling problem
چکیده انگلیسی

We are given a edge-weighted undirected graph G=(V,E)G=(V,E) and a set of labels/colors C={1,2,…,p}C={1,2,…,p}. A non-empty subset Cv⊆CCv⊆C is associated with each vertex v∈Vv∈V. A coloring of the vertices is feasible if each vertex vv is colored with a color of CvCv. A coloring uniquely defines a subset E′⊆EE′⊆E of edges having different colored endpoints. The problem of finding a feasible coloring which defines a minimum weight E′E′ is, in general, NP-hard. In this work we first propose polynomial time algorithms for some special cases, namely when the input graph is a tree, a cactus or with bounded tree-width. Then, an implicit enumeration scheme for finding an optimal coloring in the general case is described and computational results are presented.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 3, Issue 3, 1 September 2006, Pages 181–194
نویسندگان
, , ,