Covering problems in edge- and node-weighted graphs

DOI10.1016/j.disopt.2016.03.001zbMath1387.90216arXiv1404.4123OpenAlexW17598063MaRDI QIDQ1751155

Takuro Fukunaga

Publication date: 24 May 2018

Published in: Discrete Optimization, Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.4123

zbMATH Keywords

linear programming relaxationprimal-dual algorithmmulticutedge dominating setedge-weighted graphsgraph covering problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of graph theory (05C90) Linear programming (90C05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (3)

Minimum constellation covers: hardness, approximability and polynomial cases ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Weighted consensus problem for multiagent systems with edge- and node-weighted directed graphs

Cites Work

• Primal-dual approximation algorithms for integral flow and multicut in trees
• Approximation algorithms for partially covering with edges
• On the ratio of optimal integral and fractional covers
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Approximability of the capacitated \(b\)-edge dominating set problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Linear time algorithms for generalized edge dominating set problems
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Prize-Collecting Survivable Network Design in Node-Weighted Graphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The Prize-Collecting Edge Dominating Set Problem in Trees
• A Greedy Heuristic for the Set-Covering Problem
• Heuristics for the fixed cost median problem
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems
• Spider covers for prize-collecting network activation problem
• Approximating Steiner Networks with Node-Weights
• Steiner Tree Approximation via Iterative Randomized Rounding
• Matroids and integrality gaps for hypergraphic steiner tree relaxations
• Online Node-Weighted Steiner Tree and Related Problems
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem

This page was built for publication: Covering problems in edge- and node-weighted graphs