A branch and cut solver for the maximum stable set problem
From MaRDI portal
Publication:491210
DOI10.1007/s10878-009-9264-3zbMath1319.90079OpenAlexW2068262026MaRDI QIDQ491210
Dirk Oliver Theis, Marcus Oswald, Panos M. Pardalos, Hanna Seitz, Steffen Rebennack, Gerhard Reinelt
Publication date: 24 August 2015
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-009-9264-3
Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
A review on algorithms for maximum clique problems, Solving the maximum vertex weight clique problem via binary quadratic programming, A strengthened general cut-generating procedure for the stable set polytope, Fast separation for the three-index assignment problem, An adaptive multistart tabu search approach to solve the maximum clique 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, Efficient presolving methods for solving maximal covering and partial set covering location problems, Optimization Bounds from Binary Decision Diagrams, A New Approach to the Stable Set Problem Based on Ellipsoids, Graph signatures: identification and optimization, On the Lovász theta function and some variants, General cut-generating procedures for the stable set polytope, Polylithic modeling and solution approaches using algebraic modeling systems, A tutorial on branch and cut algorithms for the maximum stable set problem, Analysis of integer programming algorithms with \(L\)-partition and unimodular transformations, An exact approach to the problem of extracting an embedded network matrix, Computing maximum \(k\)-defective cliques in massive graphs, Indirect unstructured hex-dominant mesh generation using tetrahedra recombination, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, Detecting a most closeness-central clique in complex networks, Strengthened clique-family inequalities for the stable set polytope, Strengthening Chvátal-Gomory Cuts for the Stable Set Problem, A Set Covering Approach for the Double Traveling Salesman Problem with Multiple Stacks, A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs, The maximum balanced subgraph of a signed graph: applications and solution approaches
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Matrices with the Edmonds-Johnson property
- On the separation of maximally violated mod-\(k\) cuts
- Combinatorial Auctions: A Survey
- Resolution Branch and Bound and an Application: The Maximum Weighted Stable Set Problem
- Finding a Maximum Clique in an Arbitrary Graph
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- Vertex packings: Structural properties and algorithms
- Computational Experience with Stable Set Relaxations
- On the facial structure of set packing polyhedra
- Optimal Protein Structure Alignment Using Maximum Cliques
- A branch-and-price approach for the maximum weight independent set problem
- A branch-and-cut algorithm for the maximum cardinality stable set problem
