On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
From MaRDI portal
Publication:1196217
DOI10.1016/0167-6377(92)90007-PzbMath0763.90085WikidataQ111475733 ScholiaQ111475733MaRDI QIDQ1196217
David Simchi-Levi, Chung-Lun Li, S. Thomas McCormick
Publication date: 17 December 1992
Published in: Operations Research Letters (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (33)
Optimizing budget allocation for center and median points ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths ⋮ Almost optimal algorithms for diameter-optimally augmenting trees ⋮ Robustness and Strong Attack Tolerance of Low-Diameter Networks ⋮ Network design for time-constrained delivery using subgraphs ⋮ Polarization reduction by minimum‐cardinality edge additions: Complexity and integer programming approaches ⋮ Augmenting graphs to minimize the radius ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Online and Approximate Network Construction from Bounded Connectivity Constraints ⋮ Finding diameter-reducing shortcuts in trees ⋮ On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph ⋮ Online and approximate network construction from bounded connectivity constraints ⋮ Minimizing the continuous diameter when augmenting a geometric tree with a shortcut ⋮ The parametric complexity of graph diameter augmentation ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees ⋮ Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length ⋮ Augmenting graphs to minimize the diameter ⋮ Shortcuts for the circle ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks ⋮ An improved algorithm for diameter-optimally augmenting paths in a metric space ⋮ Unnamed Item ⋮ Augmenting forests to meet odd diameter requirements ⋮ A linear-time algorithm for radius-optimally augmenting paths in a metric space ⋮ Mixed covering of trees and the augmentation problem with odd diameter constraints ⋮ Improved approximability and non-approximability results for graph diameter decreasing problems ⋮ Unnamed Item ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ Mathematical programming models for some smallest-world problems ⋮ A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space ⋮ Augmenting Outerplanar Graphs to Meet Diameter Requirements ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees ⋮ Relaxed and approximate graph realizations
Cites Work
This page was built for publication: On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
