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

DOI10.1016/j.orl.2003.06.003zbMath1044.90061MaRDI QIDQ1426727

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

Spanning tree; Matrix-tree theorem; Fully polynomial approximation scheme; Bicriteria approximation

Mathematics Subject Classification ID

90C27: Combinatorial optimization

Related Items

Budgeted matching and budgeted matroid intersection via the gasoline puzzle, Approximation of min-max and min-max regret versions of some combinatorial optimization problems, The subdivision-constrained minimum spanning tree problem, A polynomial solvable minimum risk spanning tree problem with interval data, Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle, A Survey on Multiple Objective Minimum Spanning Tree Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Exact arborescences, matchings and cycles
• Matrix tree theorems
• Approximation algorithms for multi-parameter graph optimization problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• Approximation Schemes for the Restricted Shortest Path Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Bicriteria Network Design Problems
• Counting Minimum Weight Spanning Trees
• Determinant: Old Algorithms, New Insights
• The constrained minimum spanning tree problem
• A simple efficient approximation scheme for the restricted shortest path problem