On the minimum-cost -edge-connected k-subgraph problem

DOI10.1007/S10287-016-0260-7zbMATH Open1407.90241OpenAlexW2463317516MaRDI QIDQ1789587FDOQ1789587

Authors: Elham Sadeghi, Neng Fan 

Publication date: 10 October 2018

Published in: Computational Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10287-016-0260-7

Recommendations

• A constant factor approximation for minimum \(\lambda \)-edge-connected \(k\)-subgraph with metric costs
• A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
• The \(k\)-node connected subgraph problem: polyhedral analysis and branch-and-cut
• A branch-and-cut algorithm for the \(k\)-edge connected subgraph problem
• scientific article; zbMATH DE number 764407

zbMATH Keywords

minimum spanning treeinteger programminggraph connectivityvalid inequalitiesedge-connected subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Cites Work

• Title not available (Why is that?)
• Reducibility among combinatorial problems
• New branch-and-bound algorithms for \(k\)-cardinality tree problems
• Biconnectivity approximations and graph carvings
• Strong formulations for network design problems with connectivity requirements
• Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• A branch-and-cut algorithm for the \(k\)-edge connected subgraph problem
• Solving the connected dominating set problem and power dominating set problem by integer programming
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Survivable network design with degree or order constraints
• Obtaining optimal \(k\)-cardinality trees fast
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Survivable networks, linear programming relaxations and the parsimonious property
• On the Structure of Minimum-Weight k-Connected Spanning Networks
• Approximation Algorithms for Several Graph Augmentation Problems
• The minimum augmentation of any graph to aK-edge-connected graph
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
• A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs

Cited In (5)

• On the \(k\)-edge-incident subgraph problem and its variants
• A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• Optimal connected subgraphs: Integer programming formulations and polyhedra
• A constant factor approximation for minimum \(\lambda \)-edge-connected \(k\)-subgraph with metric costs

This page was built for publication: On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem

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