On minimum power connectivity problems

DOI10.1016/j.jda.2009.03.002zbMath1186.90025OpenAlexW2034019057MaRDI QIDQ972357

Yuval Lando, Zeev Nutov

Publication date: 25 May 2010

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2009.03.002

zbMATH Keywords

connectivityapproximation algorithmswireless networkspower assignment

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (8)

Survivable network activation problems ⋮ Minimum shared‐power edge cut ⋮ An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths ⋮ Construction of Minimum Power 3-Connected Subgraph with k Backbone Nodes in Wireless Sensor Networks ⋮ Approximating minimum power edge-multi-covers ⋮ Approximating minimum power covers of intersecting families and directed edge-connectivity problems ⋮ Improved approximation algorithms for minimum power covering problems ⋮ Approximation algorithms for minimum power k backbone node r-connected subgraph problem in wireless sensor networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Power optimization for connectivity problems
• Rooted \(k\)-connections in digraphs
• An application of submodular flows
• Approximating node connectivity problems via set covers
• Power consumption in packet radio networks
• Power assignment for \(k\)-connectivity in wireless ad hoc networks
• Energy-efficient wireless network design
• Matroid Intersection
• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
• Biconnectivity approximations and graph carvings
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
• Approximating Steiner Networks with Node Weights
• Approximating Minimum-Power Degree and Connectivity Problems
• Algorithms - ESA 2003
• The dense \(k\)-subgraph problem
• On rooted node-connectivity problems

This page was built for publication: On minimum power connectivity problems