Spanning Trees—Short or Small

DOI10.1137/S0895480194266331MaRDI QIDQ4881285zbMATHWikidataFDO

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)

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

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)

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.

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

Cited in

(40)

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

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)