Polyhedral approach to weighted connected matchings in general graphs

DOI10.1016/j.dam.2024.07.042MaRDI QIDQ6633527

Phablo F. S. Moura, Phillippe Samer

Publication date: 6 November 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

integer programmingcombinatorial optimizationpolyhedral combinatoricsconnected matchingsconnected subgraphsinduced connectivity

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• Greedoids
• Integer linear programming models for topology optimization in sheet metal design
• NP-completeness of some generalizations of the maximum matching problem
• On imposing connectivity constraints in integer programs
• Thinning out Steiner trees: a node-based model for uniform edge costs
• Generalized subgraph-restricted matchings in graphs
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange
• Computing convex hulls and counting integer points with \texttt{polymake}
• Establishing the matching polytope
• Integer Programming
• Odd Minimum Cut Sets and b-Matchings Revisited
• The NP-completeness column: an ongoing guide
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• Odd Minimum Cut-Sets and b-Matchings
• polymake: a framework for analyzing convex polytopes
• Imposing Connectivity Constraints in Forest Planning Models
• The Maximum Weight Connected Subgraph Problem
• Maximum matching and a polyhedron with 0,1-vertices
• Uniquely restricted matchings
• Disconnected matchings
• Optimal connected subgraphs: Integer programming formulations and polyhedra
• Weighted connected matchings

This page was built for publication: Polyhedral approach to weighted connected matchings in general graphs