Approximate min-power strong connectivity

DOI10.1137/100819540zbMATH Open1278.05133OpenAlexW2122877877MaRDI QIDQ2870520FDOQ2870520

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

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

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)

Cited In (7)

• 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
• 1.61-approximation for min-power strong connectivity with two power levels

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)