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

minimum weight spanning treesnetwork reinforcementpacking spanning treesstrength problem

Mathematics Subject Classification ID

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

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 algorithms for arborescences (and spanning trees) in capacitated graphs
• Packing Spanning Trees
• Separating from the dominant of the spanning tree polytope

Cited in

(9)

• Upgrading min-max spanning tree problem under various cost functions
• Fast approximation of matroid packing and covering
• A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
• scientific article; zbMATH DE number 871953 (Why is no real title available?)
• Increasing the Weight of Minimum Spanning Trees
• Integer Programming Formulations for Minimum Spanning Tree Interdiction
• Finding the maximum subgraph of prescribed strength
• Optimal cost augmentation and interdiction problem for the minimum spanning tree
• Mixed-integer models for complete-linkage clustering

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)