Approximating the Minimum-Degree Steiner Tree to within One of Optimal

DOI10.1006/jagm.1994.1042zbMath1321.05262OpenAlexW2066700938MaRDI QIDQ4314499

Publication date: 22 November 1995

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1994.1042

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (48)

On approximating degree-bounded network design problems ⋮ Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Small degree out‐branchings ⋮ Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ Collision-free network exploration ⋮ On some network design problems with degree constraints ⋮ Exact Algorithms for the Minimum Load Spanning Tree Problem ⋮ Network design under general wireless interference ⋮ A Spectral Approach to Network Design ⋮ Reconfiguration of spanning trees with degree constraints or diameter constraints ⋮ A unified algorithm for degree bounded survivable network design ⋮ Approximating directed weighted-degree constrained networks ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Network design with weighted degree constraints ⋮ Chain-constrained spanning trees ⋮ Lexicographic local search and the \(p\)-center problem. ⋮ Self-stabilizing minimum degree spanning tree within one from the optimal degree ⋮ A distributed approximation algorithm for the minimum degree minimum weight spanning trees ⋮ On the approximability of some degree-constrained subgraph problems ⋮ Refuting a conjecture of goemans on bounded degree spanning trees ⋮ Approximating Directed Weighted-Degree Constrained Networks ⋮ A Local-Search Algorithm for Steiner Forest ⋮ A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem ⋮ A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees ⋮ Spanning Trees With Edge Conflicts and Wireless Connectivity ⋮ The Maximum Binary Tree Problem. ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ On the complexity of connectivity in cognitive radio networks through spectrum assignment ⋮ Structure of polynomial-time approximation ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ A note on line broadcast in digraphs under the edge-disjoint paths mode ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results ⋮ Network Design with Weighted Degree Constraints ⋮ The maximum binary tree problem ⋮ Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems ⋮ Network-Design with Degree Constraints ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Degree-bounded minimum spanning trees ⋮ Fast Approximation Algorithm for Maximum Lifetime Aggregation Trees in Wireless Sensor Networks ⋮ On the Power of Planned Infections in Networks ⋮ A note on the approximability of the toughness of graphs ⋮ A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids ⋮ Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal ⋮ Unnamed Item ⋮ Spanning trees and spanning Eulerian subgraphs with small degrees

This page was built for publication: Approximating the Minimum-Degree Steiner Tree to within One of Optimal