The Optimal Design of Low-Latency Virtual Backbones

DOI10.1287/ijoc.2019.0914zbMath1456.90040OpenAlexW3016302887MaRDI QIDQ5148180

Hamidreza Validi, Austin Buchanan

Publication date: 1 February 2021

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2019.0914

zbMATH Keywords

integer programmingdelaywireless networkslatencyconnected dominating setfault-tolerant\(k\)-clubstrongly connected dominating sethop constraintlength-bounded cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Communication networks in operations research (90B18) Linear programming (90C05)

Related Items (2)

Imposing Contiguity Constraints in Political Districting Models ⋮ Solving the Distance-Based Critical Node Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Connected dominating set. Theory and applications
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• Fault diameter of Cartesian product graphs
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Construction of strongly connected dominating sets in asymmetric multihop wireless networks
• Fault diameter of interconnection networks
• On the facial structure of the set covering polytope
• Using separation algorithms to generate mixed integer model reformulations
• Mengerian theorems for paths of bounded length
• Geometric algorithms and combinatorial optimization.
• Which problems have strongly exponential complexity?
• Thinning out Steiner trees: a node-based model for uniform edge costs
• Regenerator location problem: polyhedral study and effective branch-and-cut algorithms
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Parsimonious formulations for low-diameter clusters
• On connected dominating sets of restricted diameter
• On dominating sets whose induced subgraphs have a bounded diameter
• Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
• An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
• Algorithmic construction of sets for k -restrictions
• The regenerator location problem
• The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm
• A threshold of ln n for approximating set cover
• Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
• Length-bounded cuts and flows
• The Generalized Regenerator Location Problem
• Diameter increase caused by edge deletion
• On the hardness of approximating minimization problems
• The maximum-leaf spanning tree problem: Formulations and facets
• Analytical approach to parallel repetition
• Max flows in O(nm) time, or better
• Integer priority queues with decrease key in constant time and the single source shortest paths problem
• On the complexity of \(k\)-SAT

This page was built for publication: The Optimal Design of Low-Latency Virtual Backbones