Spanning Trees—Short or Small
From MaRDI portal
Publication:4881285
DOI10.1137/S0895480194266331zbMath0855.05058arXivmath/9409222WikidataQ56474460 ScholiaQ56474460MaRDI QIDQ4881285
R. Ravi, S. S. Ravi, Ravi Sundaram, Madhav V. Marathe, Daniel J. Rosenkrantz
Publication date: 24 July 1996
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9409222
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (38)
Approximation algorithms for the covering Steiner problem ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Revisiting dynamic programming for finding optimal subtrees in trees ⋮ A new approach for the multiobjective minimum spanning tree ⋮ Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems ⋮ Budget constrained minimum cost connected medians ⋮ The density maximization problem in graphs ⋮ A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems ⋮ Compact location problems ⋮ A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem ⋮ Complexity, algorithmic, and computational aspects of a dial-a-ride type problem ⋮ A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems ⋮ Pruning 2-connected graphs ⋮ Euclidean prize-collecting Steiner forest ⋮ An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth ⋮ The complexity of minimizing certain cost metrics for \(k\)-source spanning trees. ⋮ Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem ⋮ Multi-source spanning trees: Algorithms for minimizing source eccentricities. ⋮ Degree-constrained \(k\)-minimum spanning tree problem ⋮ New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem ⋮ The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation ⋮ A note on the $k$-minimum spanning tree problem on circles ⋮ Facility location with tree topology and radial distance constraints ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ On \(k\)-Max-optimization ⋮ Simple heuristics for the rooted max tree coverage problem ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Placing green bridges optimally, with a multivariate analysis ⋮ The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices ⋮ Local search algorithms for the \(k\)-cardinality tree problem. ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs ⋮ The non-approximability of bicriteria network design problems ⋮ Integer polynomial recovery from outputs and its application to cryptanalysis of a protocol for secure sorting ⋮ A 2-approximation for the \(k\)-prize-collecting Steiner tree problem ⋮ Placing Green bridges optimally, with a multivariate analysis
This page was built for publication: Spanning Trees—Short or Small
