Exact algorithms for a discrete metric labeling problem

DOI10.1016/J.DISOPT.2006.05.009MaRDI QIDQ5920404zbMATH OpenOpenAlexFDO

Authors Arianna Alfieri, Gaia Nicosia, Andrea Pacifici

Publication date 11 January 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2006.05.009

zbMATH Keywords

graph algorithmsmultiterminal cutsmultiway cutstree-width

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Review text

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.

Recommendations

• Exact algorithms for a discrete metric labeling problem
• The Hardness of Metric Labeling
• Approximation algorithms for the metric labeling problem via a new linear programming formulation
• A constant factor approximation algorithm for a class of classification problems
• An exact algorithm for the edge coloring by total labeling problem

Cites work

• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Complexity of Finding Embeddings in a k-Tree
• Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3888924 (Why is no real title available?)
• scientific article; zbMATH DE number 975812 (Why is no real title available?)
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On rigid circuit graphs
• On weighted multiway cuts in trees
• The Complexity of Multiterminal Cuts

Cited in

(6)

• A note on exact distance labeling
• The shortest connection game
• Approximation algorithms for the metric labeling problem via a new linear programming formulation
• Solving graph partitioning problems arising in tagless cache management
• A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique
• Exact algorithms for a discrete metric labeling problem

This page was built for publication: Exact algorithms for a discrete metric labeling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5920404)