A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees

DOI10.1287/MOOR.10.4.701MaRDI QIDQ3705239zbMATH OpenOpenAlexFDO

Authors James Roskind, Robert E. Tarjan

Publication date 1985

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.10.4.701

zbMATH Keywords

polynomial timeundirected graphedge-disjoint spanning treesmatroid greedy algorithmminimum total edge cost

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35)

Recommendations

• scientific article; zbMATH DE number 3904590
• Network reinforcement
• On edge-disjoint spanning trees with small depths
• Finding minimum congestion spanning trees
• A matroid approach to finding edge connectivity and packing arborescences

Cited in

(38)

• Approximating minimum-cost graph problems with spanning tree edges
• Note on the spanning-tree packing number of lexicographic product graphs
• The generalized 3-connectivity of two kinds of regular networks
• Relay placement for fault tolerance in wireless networks in higher dimensions
• Bounds for the symmetric 2-peripatetic salesman problem
• Decomposing the hypercube Q_n into n isomorphic edge-disjoint trees
• On asymptotically optimal approach for the problem of finding several edge-disjoint spanning trees of given diameter in an undirected graph with random edge weights
• Finding totally independent spanning trees with linear integer programming
• Subgraphs decomposable into two trees and \(k\)-edge-connected subgraphs
• Edge-disjoint spanning trees and the number of maximum state circles of a graph
• On edge-disjoint spanning trees with small depths
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
• Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services
• Forests, frames, and games: Algorithms for matroid sums and applications
• Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
• Computation of equilibria and the price of anarchy in bottleneck congestion games
• Game edge-connectivity of graphs
• A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
• Sensitivity analysis for symmetric 2-peripatetic salesman problems
• Completely independent spanning trees in torus networks
• Edge-colored graphs with applications to homogeneous faults
• Lower and upper bounds for the m-peripatetic vehicle routing problem
• Sparsity-certifying graph decompositions
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• Pebble game algorithms and sparse graphs
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• Edge Partition of Toroidal Graphs into Forests in Linear Time
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Balancing connected colourings of graphs
• The parity Hamiltonian cycle problem
• Network reinforcement
• Fast algorithms via dynamic-oracle matroids
• An algorithm for min-cost edge-disjoint cycles and its applications
• Combinatorial optimization with interaction costs: complexity and solvable cases
• The edge-disjoing steiner problem in graphs
• Fully dynamic arboricity maintenance
• The generalized 4-connectivity of hypercubes
• Determining a Minimum Spanning Tree with Disjunctive Constraints

This page was built for publication: A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees

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