The Optimal Design of Low-Latency Virtual Backbones
From MaRDI portal
Publication:5148180
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
integer programmingdelaywireless networkslatencyconnected dominating setfault-tolerant\(k\)-clubstrongly connected dominating sethop constraintlength-bounded cut
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
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
