Approximate Min-Power Strong Connectivity

DOI10.1137/100819540zbMath1278.05133OpenAlexW2122877877MaRDI QIDQ2870520

Gruia Călinescu

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 algorithmsubmodular functionnetwork designapproximation algorithmspower assignment

Mathematics Subject Classification ID

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

Related Items (6)

The online broadcast range-assignment problem ⋮ The Online Broadcast Range-Assignment Problem ⋮ Dual-based approximation algorithms for cut-based network connectivity problems ⋮ 1.61-approximation for min-power strong connectivity with two power levels ⋮ Parameterized complexity of min-power asymmetric connectivity ⋮ Bounded-angle minimum spanning trees

This page was built for publication: Approximate Min-Power Strong Connectivity