Dual-based approximation algorithms for cut-based network connectivity problems

DOI10.1007/s00453-017-0356-7zbMath1392.68324arXiv1508.05567OpenAlexW2963985350MaRDI QIDQ722530

Benjamin Grimmer

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.05567

zbMATH Keywords

linear programminggraph theorynetwork designapproximation algorithmspower assignment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (1)

An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Power assignment in radio networks with two power levels
• A factor 2 approximation algorithm for the generalized Steiner network problem
• On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• On Steiner trees and minimum spanning trees in hypergraphs
• On strongly connected digraphs with bounded cycle length
• Dual power assignment optimization and fault tolerance in WSNs
• A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
• Approximate Min-Power Strong Connectivity
• Approximating the smallest k -edge connected spanning subgraph by LP-rounding
• Biconnectivity approximations and graph carvings
• Approximating the Minimum Equivalent Digraph
• Algorithms - ESA 2003

This page was built for publication: Dual-based approximation algorithms for cut-based network connectivity problems