A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.

DOI10.1016/J.ORL.2003.06.003MaRDI QIDQ1426727zbMATH OpenOpenAlexFDO

Authors Sung-Pil Hong, Sung-Jin Chung, Bum Hwan Park

Publication date 15 March 2004

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2003.06.003

zbMATH Keywords

Bicriteria approximationFully polynomial approximation schemeMatrix-tree theoremSpanning tree

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Fast approximation algorithms for computing constrained minimum spanning trees
• The constrained minimum spanning tree problem
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• Polynomial time approximation schemes for the constrained minimum spanning tree problem

Cites work

• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• A simple efficient approximation scheme for the restricted shortest path problem
• Approximation algorithms for multi-parameter graph optimization problems
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Counting Minimum Weight Spanning Trees
• Determinant: Old Algorithms, New Insights
• Exact arborescences, matchings and cycles
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• scientific article; zbMATH DE number 969179 (Why is no real title available?)
• scientific article; zbMATH DE number 3047763 (Why is no real title available?)
• Matrix tree theorems
• The constrained minimum spanning tree problem

Cited in

(20)

• The subdivision-constrained minimum spanning tree problem
• A polynomial solvable minimum risk spanning tree problem with interval data
• Fast approximation algorithms for computing constrained minimum spanning trees
• Exact algorithms for OWA-optimization in multiobjective spanning tree problems
• Approximate Pareto sets of minimal size for multi-objective optimization problems
• Exact algorithms for finding constrained minimum spanning trees
• When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem
• Implicit cover inequalities
• Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
• A Survey on Multiple Objective Minimum Spanning Tree Problems
• General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
• Polynomial time approximation schemes for the constrained minimum spanning tree problem
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• Covers and approximations in multiobjective optimization
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• On the minimum \(s-t\) cut problem with budget constraints
• Lower bounds for matroid optimization problems with a linear constraint
• Strongly polynomial-time approximation for a class of bicriteria problems.
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems

This page was built for publication: A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1426727)