Minimum-weight two-connected spanning networks

From MaRDI portal
Publication:582215

DOI10.1007/BF01585735zbMath0689.90071MaRDI QIDQ582215

Clyde l. Monma, Beth Spellman Munson, William R. Pulleyblank

Publication date: 1990

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)




Related Items

Two-edge connected spanning subgraphs and polyhedra, Survivable network design with shared-protection routing, Bounding component sizes of two-connected Steiner networks, Orientation-based models for \(\{0,1,2\}\)-survivable network design: theory and practice, 2-change for k-connected networks, Capacitated \(m\) two-node survivable star problem, On perfectly two-edge connected graphs, Cutting plane versus compact formulations for uncertain (integer) linear programs, On two-connected subgraph polytopes, The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs, On finding two-connected subgraphs in planar graphs, A bootstrap heuristic for designing minimum cost survivable networks, Graph fragmentation problem: analysis and synthesis, Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices, On a partition LP relaxation for min-cost 2-node connected spanning subgraphs, The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\), Survivable minimum bottleneck networks, On minimally \(k\)-edge-connected graphs and shortest \(k\)-edge-connected Steiner networks, Steiner problem in networks: A survey, Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane, Shorter tours and longer detours: uniform covers and a bit beyond, Computing minimum 2‐edge‐connected Steiner networks in the Euclidean plane, Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems, Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs, On the structure and complexity of the 2-connected Steiner network problem in the plane, Linear bounds for on-line Steiner problems, Analysis of the Held-Karp lower bound for the asymmetric TSP, Survivable networks, linear programming relaxations and the parsimonious property, Two-connected Steiner networks: structural properties, On the dominant of the Steiner 2-edge connected subgraph polytope, On the Steiner 2-edge connected subgraph polytope, Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems, Polyhedral structure of the 4-node network design problem, Using a hybrid of exact and genetic algorithms to design survivable networks, The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation, On the integrality ratio for tree augmentation, The box-TDI system associated with 2-edge connected spanning subgraphs, Full complexity analysis of the diameter-constrained reliability, Securely Connected Facility Location in Metric Graphs, The capacitated m two node survivable star problem, On shortest three-edge-connected Steiner networks with Euclidean distance, Directed Steiner problems with connectivity constraints



Cites Work