LP-relaxations for tree augmentation (Q1706120)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	LP-relaxations for tree augmentation	scientific article

Statements

scholarly article

0 references

LP-relaxations for tree augmentation (English)

0 references

0 references

0 references

Discrete Applied Mathematics

0 references

publication date

21 March 2018

0 references

full work available at URL

https://drops.dagstuhl.de/opus/volltexte/2016/6636/

0 references

zbMATH Keywords

tree augmentation

0 references

LP-relaxation

0 references

Laminar family

0 references

approximation algorithm

0 references

MaRDI profile type

MaRDI publication profile

0 references

Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

0 references

Approximating (unweighted) tree augmentation via lift-and-project. II

0 references

0 references

On the integrality ratio for tree augmentation

0 references

A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius

0 references

0 references

A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

0 references

0 references

Approximation Algorithms for Several Graph Augmentation Problems

0 references

On the relationship between the biconnectivity augmentation and traveling salesman problems

0 references

A factor 2 approximation algorithm for the generalized Steiner network problem

0 references

0 references

Approximation Algorithms for Graph Augmentation

0 references

A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2

0 references

Iterative Methods in Combinatorial Optimization

0 references

Covering a laminar family by leaf to leaf links

0 references

An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree

0 references

0 references

Combinatorial Optimization. Polyhedra and efficiency. CD-ROM

0 references

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

0 references

A primal-dual approximation algorithm for generalized Steiner network problems

0 references

Identifiers

zbMATH Open document ID

0 references

10.1016/j.dam.2017.12.033

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1706120

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q1706120&oldid=36379819"