A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
DOI10.1287/MOOR.10.4.701zbMATH Open0581.90093OpenAlexW2124608963MaRDI QIDQ3705239FDOQ3705239
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
Recommendations
polynomial timeundirected graphedge-disjoint spanning treesmatroid greedy algorithmminimum total edge cost
Programming involving graphs or networks (90C35) Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35)
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
- Bounds for the symmetric 2-peripatetic salesman problem
- Relay placement for fault tolerance in wireless networks in higher dimensions
- 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
- Decomposing the hypercube \(Q_n\) into \(n\) isomorphic edge-disjoint trees
- 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
- Sensitivity analysis for symmetric 2-peripatetic salesman problems
- A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
- 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
- Fast algorithms via dynamic-oracle matroids
- The parity Hamiltonian cycle problem
- Network reinforcement
- The edge-disjoing steiner problem in graphs
- Combinatorial optimization with interaction costs: complexity and solvable cases
- An algorithm for min-cost edge-disjoint cycles and its applications
- 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)
