Spider Covering Algorithms for Network Design Problems

DOI10.1007/978-981-10-6147-9_3zbMath1397.90077OpenAlexW2759558882MaRDI QIDQ4689626

Takuro Fukunaga

Publication date: 16 October 2018

Published in: Combinatorial Optimization and Graph Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-981-10-6147-9_3

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Combinatorial aspects of packing and covering (05B40)

Cites Work

• Unnamed Item
• Unnamed Item
• Survivable network activation problems
• Improved approximation algorithms for directed Steiner forest
• A note on the prize collecting traveling salesman problem
• Covering problems in edge- and node-weighted graphs
• Approximating subset \(k\)-connectivity problems
• Efficient recovery from power outage (extended abstract)
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
• Prize-Collecting Survivable Network Design in Node-Weighted Graphs
• Set connectivity problems in undirected graphs and the directed steiner network problem
• Polylogarithmic inapproximability
• Dynamic Steiner Tree Problem
• Online Buy-at-Bulk Network Design
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Approximation Algorithms for Directed Steiner Problems
• Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems
• Spider covers for prize-collecting network activation problem
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• 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

This page was built for publication: Spider Covering Algorithms for Network Design Problems