Algorithms and complexity for a class of combinatorial optimization problems with labelling
type: Item
instance of: scholarly article
title: Algorithms and complexity for a class of combinatorial optimization problems with labelling
zbMATH Open document ID: 1469.90126
author: Zishen Yang
author: Wei Wang
author: Majun Shi
published in: Journal of Optimization Theory and Applications
publication date: 2021-06-15T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 7359099
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: approximation algorithm
zbMATH Keywords: problem labelling
zbMATH Keywords: sublobular cover
zbMATH Keywords: \(\mathcal{NP}\)-hardness
zbMATH Keywords: inapproximation
MaRDI profile type: Publication
full work available at URL: s10957-020-01802-x
OpenAlex ID: W3120026953
cites work: The minimum labeling spanning trees
cites work: On the minimum label spanning tree problem
cites work: A note on the minimum label spanning tree.
cites work: A threshold of ln n for approximating set cover
cites work: Spanning trees with many or few colors in edge-colored graphs
cites work: Paths and cycles in colored graphs
cites work: Approximation and hardness results for label cut and related problems
cites work: Transversals of latin squares and their generalizations
cites work: Some Matching Problems for Bipartite Graphs
cites work: Coloured matchings in bipartite graphs
cites work: Least and most colored bases
cites work: Q4952637
cites work: Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
cites work: Geometric red-blue set cover for unit squares and related problems
cites work: Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
cites work: On interdependent failure resilient multi-path routing in smart grid communication network
cites work: Q4314864
cites work: The parameterized complexity of some minimum label problems
cites work: The complexity of bottleneck labeled graph problems
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Design and analysis of approximation algorithms
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q4198056
cites work: The connected vertex cover problem in \(k\)-regular graphs
cites work: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
DOI: 10.1007/S10957-020-01802-X
Recommended article: Algorithmic complexity of proper labeling problems
Recommended article: Algorithmic Aspects of the S-Labeling Problem
Recommended article: Algorithmic expedients for the \(S\)-labeling problem
Recommended article: Q3836963
Recommended article: Q4997758
Recommended article: Q4316053
Recommended article: The \(S\)-\textsc{labeling} problem: an algorithmic tour
Recommended article: Exact Algorithms for Generalized Combinatorial Optimization Problems
Recommended article: The parameterized complexity of some minimum label problems
description: scientific article; zbMATH DE number 7359099