scientific article; zbMATH DE number 742977
zbMATH Open0818.90124MaRDI QIDQ4763416FDOQ4763416
Authors: Michel X. Goemans, David P. Williamson 
Publication date: 11 April 1995
Title of this publication is not available (Why is that?)
Recommendations
- A General Approximation Technique for Constrained Forest Problems
- Complexity and approximation of the constrained forest problem
- A \(\frac{3}{2}\) approximation for a constrained forest problem
- A class of heuristics for the constrained forest problem
- Another greedy heuristic for the constrained forest problem
- scientific article; zbMATH DE number 1833410
- Covering a graph with a constrained forest (extended abstract)
- Approximating the Spanning k-Tree Forest Problem
- Approximating the spanning \(k\)-tree forest problem
- The maximum agreement forest problem: Approximation algorithms and computational experiments
minimum spanning treeshortest pathcoveringSteiner treetraveling salesmangraph problemsapproximation techniqueminimum-weight perfect matching
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)
Cited In (34)
- Approximating minimum-cost graph problems with spanning tree edges
- On the approximability of dense Steiner problems
- A primal-dual approximation algorithm for generalized Steiner network problems
- Survivable networks, linear programming relaxations and the parsimonious property
- The multi-weighted spanning tree problem
- A 3/2-approximation algorithm for some minimum-cost graph problems
- Complexity and approximation of the constrained forest problem
- On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
- Online constrained forest and prize-collecting network design
- The point-to-point connection problem - analysis and algorithms
- Modifying edges of a network to obtain short subgraphs
- Rounding algorithms for covering problems
- A data structure for bicategories, with application to speeding up an approximation algorithm
- New approximation results on graph matching and related problems
- A greedy heuristic for a minimum-weight forest problem
- Fast and Simple Algorithms for Weighted Perfect Matching
- Approximation results for a min-max location-routing problem
- Approximating the maximum internal spanning tree problem
- A \(\frac{3}{2}\) approximation for a constrained forest problem
- Imposing Connectivity Constraints in Forest Planning Models
- Navigating Forest Straight-Line Programs in Constant Time
- A stabilized column generation scheme for the traveling salesman subtour problem
- A note on the subadditive network design problem
- A class of heuristics for the constrained forest problem
- Matching Based Augmentations for Approximating Connectivity Problems
- Approximation Algorithms for a Network Design Problem
- Exact methods for solving the elementary shortest and longest path problems
- Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
- New primal and dual matching heuristics
- The parsimonious property of cut covering problems and its applications
- On survivable network polyhedra
- Fractional covers for forests and matchings
- A General Approximation Technique for Constrained Forest Problems
- Linear bounds for on-line Steiner problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4763416)
