Spider covering algorithms for network design problems

DOI10.1007/978-981-10-6147-9_3MaRDI QIDQ4689626zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Spider covers and their applications
• Spider covers for prize-collecting network activation problem
• Spider covers for prize-collecting network activation problem
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• scientific article; zbMATH DE number 1302025

Cites work

• scientific article; zbMATH DE number 1263279 (Why is no real title available?)
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A note on the prize collecting traveling salesman problem
• Approximating Steiner networks with node-weights
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Approximating subset \(k\)-connectivity problems
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Approximation Algorithms for Directed Steiner Problems
• Approximation algorithms for nonuniform buy-at-bulk network design
• Dynamic Steiner Tree Problem
• Efficient recovery from power outage (extended abstract)
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Improved approximation algorithms for directed Steiner forest
• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• Online Buy-at-Bulk Network Design
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• Online node-weighted Steiner tree and related problems
• Polylogarithmic inapproximability
• Prize-collecting survivable network design in node-weighted graphs
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Spider covers for prize-collecting network activation problem
• Steiner tree approximation via iterative randomized rounding
• Survivable network activation problems
• Survivable network design problems in wireless networks

Cited in

(3)

• Spider covers for prize-collecting network activation problem
• Spider covers and their applications
• Spider covers for prize-collecting network activation problem

This page was built for publication: Spider covering algorithms for network design problems

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