Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph Problem.

Sylvia C. Boyd Philippe Legault

Published in: CoRR (2015)

Keyphrases

minimum cost
np hard
undirected graph
lower bound
worst case
approximation algorithms
network flow

spanning tree
upper bound
network flow problem
capacity constraints
optimal solution
edge weights
edge detection

network simplex algorithm
linear programming
minimum cost flow
graph mining
np complete
integer programming
branch and bound algorithm

connected components
scheduling problem
objective function
directed graph
weighted graph
computational complexity
maximum weight