scientific article; zbMATH DE number 1002204

MaRDI QIDQ3129922zbMATH OpenFDO

Authors Giora Slutzki, David Eppstein, David Fernández-Baca

Publication date 28 May 1997

zbMATH Keywords

minimum ratio spanning tree problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Using sparsification for parametric minimum spanning tree problems
• scientific article; zbMATH DE number 1512690
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• A practical minimum spanning tree algorithm using the cycle property

Cited in

(15)

• Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights
• Decomposable multi-parameter matroid optimization problems.
• Upgrading min-max spanning tree problem under various cost functions
• An approximation algorithm for a general class of multi-parametric optimization problems
• An approximation algorithm for a general class of parametric optimization problems
• An FPTAS for the knapsack problem with parametric weights
• An FPTAS for the parametric knapsack problem
• A general approximation method for bicriteria minimization problems
• Finding the shortest bottleneck edge in a parametric minimum spanning tree
• Possibilistic bottleneck combinatorial optimization problems with ill-known weights
• Using sparsification for parametric minimum spanning tree problems
• Approximation schemes for the parametric knapsack problem
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• A stronger lower bound on parametric minimum spanning trees
• A stronger lower bound on parametric minimum spanning trees

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 Q3129922)