Approximate min-power strong connectivity

DOI10.1137/100819540MaRDI QIDQ2870520zbMATH OpenOpenAlexFDO

Authors Gruia Calinescu

Publication date 21 January 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/100819540

zbMATH Keywords

greedy algorithmapproximation algorithmsnetwork designsubmodular functionpower assignment

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Connectivity (05C40) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10)

Recommendations

• Min-power strong connectivity
• 1.61-approximation for min-power strong connectivity with two power levels
• On minimum power connectivity problems
• On Minimum Power Connectivity Problems
• Power optimization for connectivity problems

Cited in

(7)

• 1.61-approximation for min-power strong connectivity with two power levels
• Min-power strong connectivity
• Dual-based approximation algorithms for cut-based network connectivity problems
• Bounded-angle minimum spanning trees
• The Online Broadcast Range-Assignment Problem
• The online broadcast range-assignment problem
• Approximating minimum-power degree and connectivity problems

This page was built for publication: Approximate min-power strong connectivity

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