Spanning Trees—Short or Small

DOI10.1137/S0895480194266331zbMATH Open0855.05058arXivmath/9409222WikidataQ56474460 ScholiaQ56474460MaRDI QIDQ4881285FDOQ4881285

Authors: R. Ravi, Ravi Sundaram, S. S. Ravi, Madhav V. Marathe, Daniel J. Rosenkrantz 

Publication date: 24 July 1996

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number $k$ of nodes are required to be connected in the solution. A prototypical example is the $k$MST problem in which we require a tree of minimum weight spanning at least $k$ nodes in an edge-weighted graph. We show that the $k$MST problem is NP-hard even for points in the Euclidean plane. We provide approximation algorithms with performance ratio $2sqrtk$ for the general edge-weighted case and $O(k^{1/4})$ for the case of points in the plane. Polynomial-time exact solutions are also presented for the class of decomposable graphs which includes trees, series-parallel graphs, and bounded bandwidth graphs, and for points on the boundary of a convex region in the Euclidean plane. We also investigate the problem of finding short trees, and more generally, that of finding networks with minimum diameter. A simple technique is used to provide a polynomial-time solution for finding $k$-trees of minimum diameter. We identify easy and hard problems arising in finding short networks using a framework due to T. C. Hu.

Full work available at URL: https://arxiv.org/abs/math/9409222

Recommendations

• scientific article; zbMATH DE number 889958
• Circular choosability of graphs
• \((4m,m)\)-choosability of plane graphs
• Minimum choosability of planar graphs
• On the acyclic choosability of graphs

zbMATH Keywords

connected graphlist coloringchoosabilitychordal graphsplanar graphscolor

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cited In (40)

• Facility location with tree topology and radial distance constraints
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• Multi-source spanning trees: Algorithms for minimizing source eccentricities.
• A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems
• Placing Green bridges optimally, with a multivariate analysis
• Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
• Revisiting dynamic programming for finding optimal subtrees in trees
• Pruning 2-connected graphs
• The non-approximability of bicriteria network design problems
• Degree-constrained \(k\)-minimum spanning tree problem
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
• Simple heuristics for the rooted max tree coverage problem
• The complexity of minimizing certain cost metrics for \(k\)-source spanning trees.
• Budget constrained minimum cost connected medians
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• Local search algorithms for the \(k\)-cardinality tree problem.
• A new approach for the multiobjective minimum spanning tree
• A note on the $k$-minimum spanning tree problem on circles
• Euclidean prize-collecting Steiner forest
• On \(k\)-Max-optimization
• Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
• The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices
• Placing green bridges optimally, with a multivariate analysis
• Maintaining spanning trees of small diameter
• An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth
• Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems
• Flexible list colorings in graphs with special degeneracy conditions
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• Compact location problems
• Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
• Integer polynomial recovery from outputs and its application to cryptanalysis of a protocol for secure sorting
• Approximation algorithms for the covering Steiner problem
• Complexity, algorithmic, and computational aspects of a dial-a-ride type problem
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Differential approximation of NP-hard problems with equal size feasible solutions
• New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem
• A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems
• The density maximization problem in graphs
• A 2-approximation for the \(k\)-prize-collecting Steiner tree problem

This page was built for publication: Spanning Trees—Short or Small

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