A linear programming approach to increasing the weight of all minimum spanning trees

DOI10.1002/NET.20242MaRDI QIDQ3548723zbMATH OpenOpenAlexFDO

Authors Mourad Baïou, Francisco Barahona

Publication date 17 December 2008

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20242

zbMATH Keywords

packing spanning treesnetwork reinforcementminimum weight spanning treesstrength problem

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Trees (05C05) Extremal problems in graph theory (05C35)

Recommendations

• Increasing the Weight of Minimum Spanning Trees
• scientific article; zbMATH DE number 871953
• Incremental minimum spanning tree algorithms
• Minimum spanning trees in networks with varying edge weights
• Efficient Algorithms for the Inverse Spanning-Tree Problem

Cites work

• A faster algorithm for computing the strength of a network
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Computing the Strength of a Graph
• Edge-Disjoint Spanning Trees of Finite Graphs
• Increasing the Weight of Minimum Spanning Trees
• Network reinforcement
• New primal and dual matching heuristics
• On the Problem of Decomposing a Graph into n Connected Factors
• Optimal attack and reinforcement of a network
• Packing Spanning Trees
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Separating from the dominant of the spanning tree polytope

Cited in

(5)

• Fast approximation of matroid packing and covering
• Integer Programming Formulations for Minimum Spanning Tree Interdiction
• Increasing the Weight of Minimum Spanning Trees
• Upgrading min-max spanning tree problem under various cost functions
• A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs

This page was built for publication: A linear programming approach to increasing the weight of all minimum spanning trees

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