Approximating the Minimum-Degree Steiner Tree to within One of Optimal
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 742978
- Approximating minimum bounded degree spanning trees to within one of optimal
- Low-Degree Spanning Trees of Small Weight
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- scientific article; zbMATH DE number 1445376
Cited in
(65)- Degree-bounded minimum spanning trees
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
- Lexicographic local search and the \(p\)-center problem.
- Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations
- Chain-constrained spanning trees
- Refuting a conjecture of goemans on bounded degree spanning trees
- Binary Steiner trees: structural results and an exact solution approach
- A note on line broadcast in digraphs under the edge-disjoint paths mode
- A note on the approximability of the toughness of graphs
- The maximum binary tree problem
- Near-linear time algorithm for approximate minimum degree spanning trees
- On approximating degree-bounded network design problems
- Bounded-degree light approximate shortest-path trees in doubling metrics
- Spanning trees and spanning Eulerian subgraphs with small degrees
- What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
- Collision-free network exploration
- Sharp separation and applications to exact and parameterized algorithms
- Network design under general wireless interference
- Fast approximation algorithm for maximum lifetime aggregation trees in wireless sensor networks
- Network-design with degree constraints
- A degree based approach to find Steiner trees
- Connectivity oracles for graphs subject to vertex failures
- Fast algorithms for parameterized problems with relaxed disjointness constraints
- Approximating Directed Weighted-Degree Constrained Networks
- On some network design problems with degree constraints
- Degree-Constrained Subgraph Problems: Hardness and Approximation Results
- Network Design with Weighted Degree Constraints
- scientific article; zbMATH DE number 5629898 (Why is no real title available?)
- Network design with weighted degree constraints
- A Polynomial Algorithm for the Degree-Constrained Minimum K-Tree Problem
- A distributed approximation algorithm for the minimum degree minimum weight spanning trees
- On the approximability of some degree-constrained subgraph problems
- scientific article; zbMATH DE number 2081108 (Why is no real title available?)
- scientific article; zbMATH DE number 1563034 (Why is no real title available?)
- scientific article; zbMATH DE number 742978 (Why is no real title available?)
- Small degree out‐branchings
- On the Power of Planned Infections in Networks
- A local-search algorithm for Steiner forest
- Spanning trees with edge conflicts and wireless connectivity
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- Exact Algorithms for the Minimum Load Spanning Tree Problem
- A Spectral Approach to Network Design
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Budgeted matching and budgeted matroid intersection via the gasoline puzzle
- Approximating minimum bounded degree spanning trees to within one of optimal
- Matroidal degree-bounded minimum spanning trees
- The Maximum Binary Tree Problem.
- Reconfiguration of spanning trees with degree constraints or diameter constraints
- Approximating directed weighted-degree constrained networks
- Self-stabilizing minimum degree spanning tree within one from the optimal degree
- NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
- Approximating long cycle above Dirac's guarantee
- An optimal absolute approximation algorithm for computing k disjoint restricted shortest paths
- On better heuristics for Steiner minimum trees
- Better decremental and fully dynamic sensitivity oracles for subgraph connectivity
- Degrees and network design: new problems and approximations
- Structure of polynomial-time approximation
- Finding spanning trees with perfect matchings
- Fast combinatorial algorithms for efficient sortation
- Fast combinatorial algorithms for efficient sortation
- Near-optimal vertex fault-tolerant labels for Steiner connectivity
- A unified algorithm for degree bounded survivable network design
- A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
- Approximating the selected-internal Steiner tree
This page was built for publication: Approximating the Minimum-Degree Steiner Tree to within One of Optimal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4314499)
