Extended formulations for the \(A\)-cut problem

DOI10.1007/BF02592096zbMath0848.90119OpenAlexW2074311408MaRDI QIDQ1915806

Jonathan H. Owen, Sunil Chopra

Publication date: 9 October 1996

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02592096

zbMATH Keywords

valid inequalitiesundirected graphLP-relaxationsminimum cost set of edges

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Related Items (8)

On the (near) optimality of extended formulations for multi-way cut in social networks ⋮ Cluster analysis and mathematical programming ⋮ Extended formulations for the \(A\)-cut problem ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ Nonlinear formulations and improved randomized approximation algorithms for multicut problems ⋮ The critical node detection problem in networks: a survey ⋮ A note on formulations for the \(A\)-partition problem on hypergraphs ⋮ An improved approximation algorithm of MULTIWAY CUT.

Cites Work

• Unnamed Item
• The planar multiterminal cut problem
• The ellipsoid method and its consequences in combinatorial optimization
• Extended formulations for the \(A\)-cut problem
• The perfectly matchable subgraph polytope of a bipartite graph
• A Branch-and-Cut Approach to a Traveling Salesman Problem with Side Constraints
• On the multiway cut polyhedron
• A Polynomial Algorithm for the k-cut Problem for Fixed k

This page was built for publication: Extended formulations for the \(A\)-cut problem