A branch-and-cut algorithm for the maximum cardinality stable set problem

DOI10.1016/S0167-6377(00)00060-2zbMath1054.90098OpenAlexW2157693956MaRDI QIDQ5940036

Fabrizio Rossi, Stefano Smriglio

Publication date: 30 July 2002

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(00)00060-2

zbMATH Keywords

Branch-and-cutRank inequalityStable set

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (30)

A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems ⋮ A polyhedral study of the maximum stable set problem with weights on vertex-subsets ⋮ A review on algorithms for maximum clique problems ⋮ A strengthened general cut-generating procedure for the stable set polytope ⋮ An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem ⋮ A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ Strong lift-and-project cutting planes for the stable set problem ⋮ Total coloring and total matching: polyhedra and facets ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ Drainage area maximization in unconventional hydrocarbon fields with integer linear programming techniques ⋮ An extended formulation for the 1‐wheel inequalities of the stable set polytope ⋮ Optimization Bounds from Binary Decision Diagrams ⋮ A branch and cut solver for the maximum stable set problem ⋮ A New Approach to the Stable Set Problem Based on Ellipsoids ⋮ On the Lovász theta function and some variants ⋮ General cut-generating procedures for the stable set polytope ⋮ A tutorial on branch and cut algorithms for the maximum stable set problem ⋮ The maximum common edge subgraph problem: A polyhedral investigation ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ A set packing model for the ground holding problem in congested networks ⋮ Analysis of a generalized linear ordering problem via integer programming ⋮ An exact approach to the problem of extracting an embedded network matrix ⋮ A branch-and-cut algorithm for the pallet loading problem ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ Strengthened clique-family inequalities for the stable set polytope ⋮ Strengthening Chvátal-Gomory Cuts for the Stable Set Problem ⋮ The maximum balanced subgraph of a signed graph: applications and solution approaches

Cites Work

• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization
• Separating lifted odd-hole inequalities to solve the index selection problem
• An exact algorithm for the maximum stable set problem
• Conflict graphs in solving integer programming problems
• Finding a Maximum Clique in an Arbitrary Graph
• Design and Implementation of an Interactive Optimization System for Telephone Network Planning
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Set Partitioning: A survey
• Further facet generating procedures for vertex packing polytopes
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• Compositions of Graphs and Polyhedra II: Stable Sets

This page was built for publication: A branch-and-cut algorithm for the maximum cardinality stable set problem