Exact algorithms for a discrete metric labeling problem (Q5920404)
From MaRDI portal
scientific article; zbMATH DE number 5225176
Language | Label | Description | Also known as |
---|---|---|---|
English | Exact algorithms for a discrete metric labeling problem |
scientific article; zbMATH DE number 5225176 |
Statements
Exact algorithms for a discrete metric labeling problem (English)
0 references
11 January 2008
0 references
Let \(G=(V,E)\) be an edge-weighted undirected graph, and \(C\) be a finite set of colors. Furthermore for each vertex \(v\) a non-empty subset \(C_v\) of colors is associated. A vertex coloring \(\varphi\) is feasible if for each \(v\) we have \(\varphi(v) \in C_v.\) To find a feasible coloration which minimizes the total edge weights of the color-changing edges (edges with differently colored vertices) is called discrete metric labeling problem, and was introduced by this paper. This is a special case of the metric labeling problem of J. Kleinberg and E. Tardos (therefore the approximation algorithm of the latter also works on it). The problem is also closely related to the colored multiway cut problem of P. L. Erdős and L. A. Székely. Finally the problem provides a mean to deal with flexible manufacturing systems. The main contributions of the paper is the exact solutions of discrete metric labeling problem for trees, cycles and graphs with small tree-width. It also introduces a general branch and bound algorithm to solve the general (NP-hard) problem.
0 references
multiterminal cuts
0 references
multiway cuts
0 references
tree-width
0 references
graph algorithms
0 references