Algorithms and complexity for a class of combinatorial optimization problems with labelling

DOI10.1007/s10957-020-01802-xzbMath1469.90126OpenAlexW3120026953MaRDI QIDQ2031932

Majun Shi, Zishen Yang, Wei Wang

Publication date: 15 June 2021

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10957-020-01802-x

zbMATH Keywords

combinatorial optimizationapproximation algorithm\(\mathcal{NP}\)-hardnessinapproximationproblem labellingsublobular cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation and hardness results for label cut and related problems
• Design and analysis of approximation algorithms
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• Transversals of latin squares and their generalizations
• Coloured matchings in bipartite graphs
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
• On interdependent failure resilient multi-path routing in smart grid communication network
• A note on the minimum label spanning tree.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The parameterized complexity of some minimum label problems
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Geometric red-blue set cover for unit squares and related problems
• Least and most colored bases
• The connected vertex cover problem in \(k\)-regular graphs
• A threshold of ln n for approximating set cover
• Some Matching Problems for Bipartite Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Spanning trees with many or few colors in edge-colored graphs
• The complexity of bottleneck labeled graph problems

This page was built for publication: Algorithms and complexity for a class of combinatorial optimization problems with labelling