On the relationship between the biconnectivity augmentation and traveling salesman problems
From MaRDI portal
Publication:1165162
DOI10.1016/0304-3975(82)90059-7zbMath0486.90082OpenAlexW2038858023MaRDI QIDQ1165162
Greg N. Frederickson, Joseph F. Ja'Ja'
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90059-7
traveling salesmanapproximation algorithmweighted graphworst-case analysisgraph augmentationbiconnected subgraphbiconnectivity augmentation
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05)
Related Items
Two-edge connected spanning subgraphs and polyhedra, Better algorithms for minimum weight vertex-connectivity problems, Bounding component sizes of two-connected Steiner networks, Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem, Survivable network design: the capacitated minimum spanning network problem, On perfectly two-edge connected graphs, A simple LP-based approximation algorithm for the matching augmentation problem, A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius, Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph, The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm, On a partition LP relaxation for min-cost 2-node connected spanning subgraphs, LP-relaxations for tree augmentation, Shorter tours and longer detours: uniform covers and a bit beyond, On the structure and complexity of the 2-connected Steiner network problem in the plane, A \(4+\epsilon\) approximation for \(k\)-connected subgraphs, On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality, Covering a laminar family by leaf to leaf links, Minimum-weight two-connected spanning networks, A branch-and-cut algorithm for the k-edge connected subgraph problem, Approximation algorithms for graph augmentation, A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius, Securely Connected Facility Location in Metric Graphs, The traveling salesman problem on a graph and some related integer polyhedra, Strongly Connected Spanning Subgraph for Almost Symmetric Networks, On small-depth tree augmentations, Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Approximation algorithms for combinatorial problems
- An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
- Priority queues with update and finding minimum spanning trees
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Parallel concepts in graph theory
- Dynamic Programming Treatment of the Travelling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- Approximation Algorithms for Several Graph Augmentation Problems
- On the Computational Complexity of Combinatorial Problems
- Augmentation Problems
- Smallest Augmentations to Biconnect a Graph
- Finding Minimum Spanning Trees
- Maximum matching and a polyhedron with 0,1-vertices
- The complexity of theorem-proving procedures
