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

approximation algorithmsgreedy algorithmnetwork designpower assignmentsubmodular function

Mathematics Subject Classification ID

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

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)

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