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)
minimum-weight, two-connected networkoptimal traveling salesman cyclespanning networksymmetric nonnegative distance functiontwo-connectivity
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
- Matchings in regular graphs
- On the relationship between the biconnectivity augmentation and traveling salesman problems
- On the symmetric travelling salesman problem I: Inequalities
- On the symmetric travelling salesman problem II: Lifting theorems and facets
- On two geometric problems related to the travelling salesman problem
- Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
- On the Structure of Minimum-Weight k-Connected Spanning Networks
- The traveling salesman problem: An update of research
- The traveling salesman problem on a graph and some related integer polyhedra
- Convexity and the Steiner tree problem
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Linear-time computability of combinatorial problems on series-parallel graphs
- On some connectivity properties of Eulerian graphs
- Augmentation Problems
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Tight bounds for christofides' traveling salesman heuristic
- Maximum matching and a polyhedron with 0,1-vertices
- Steiner Minimal Trees
- The steiner problem in graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
