Packing cuts in undirected graphs

DOI10.1002/NET.20008MaRDI QIDQ4812395zbMATH OpenOpenAlexFDO

Authors Alberto Caprara, Alessandro Panconesi, Romeo Rizzi

Publication date 20 August 2004

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20008

zbMATH Keywords

complexityapproximationindependent setpackinglinear programming relaxationedge-disjoint cuts

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 1875440
• Publication:4938789
• A branch-price-and-cut algorithm for packing cuts in undirected graphs
• Packing multiway cuts in capacitated graphs
• Approximability of Packing Disjoint Cycles

Cites work

• scientific article; zbMATH DE number 1256679 (Why is no real title available?)
• scientific article; zbMATH DE number 1405804 (Why is no real title available?)
• Geometric algorithms and combinatorial optimization

Cited in

(9)

• Approximability of Packing Disjoint Cycles
• scientific article; zbMATH DE number 4162902 (Why is no real title available?)
• Packing multiway cuts in capacitated graphs
• A branch-price-and-cut algorithm for packing cuts in undirected graphs
• A new upper bound for unconstrained two-dimensional cutting and packing
• Directed cut transversal packing for source-sink connected graphs
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• scientific article; zbMATH DE number 1405804 (Why is no real title available?)
• scientific article; zbMATH DE number 1875440 (Why is no real title available?)

This page was built for publication: Packing cuts in undirected graphs

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