The k-node connected subgraph problem: polyhedral analysis and branch-and-cut

DOI10.1016/J.ENDM.2016.03.016MaRDI QIDQ325409zbMATH OpenOpenAlexFDO

Authors I. Diarrassouba, Meriem Mahjoub, Raouia Taktak, A. R. Mahjoub

Publication date 18 October 2016

Full work available at URL https://doi.org/10.1016/j.endm.2016.03.016

zbMATH Keywords

polytopeseparationbranch-and-cut algorithm\(k\)-node connected graph

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Integer programming (90C10)

Recommendations

• A branch-and-cut algorithm for the \(k\)-edge connected subgraph problem
• Polyhedral study of the connected subgraph problem
• scientific article; zbMATH DE number 764407
• On the linear relaxation of the 2-node connected subgraph polytope
• The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points.

Cites work

• scientific article; zbMATH DE number 176255 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A branch-and-cut algorithm for the \(k\)-edge connected subgraph problem
• On the linear relaxation of the 2-node connected subgraph polytope
• The k-Edge-Connected Spanning Subgraph Polyhedron
• The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points.
• k-edge connected polyhedra on series-parallel graphs

Cited in

(14)

• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• Mixed-integer programming techniques for the connected max-\(k\)-cut problem
• Polyhedral analysis and branch-and-cut for the structural analysis problem
• On the \(k\)-edge-incident subgraph problem and its variants
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• On imposing connectivity constraints in integer programs
• \(k\)-edge subgraph problems
• Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems
• The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation
• Polyhedral study of the connected subgraph problem
• On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
• Optimal connected subgraphs: Integer programming formulations and polyhedra
• A branch-and-cut algorithm for the \(k\)-edge connected subgraph problem
• scientific article; zbMATH DE number 764407 (Why is no real title available?)

This page was built for publication: The \(k\)-node connected subgraph problem: polyhedral analysis and branch-and-cut

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