An exact algorithm for the maximum stable set problem
From MaRDI portal
Publication:1328431
DOI10.1007/BF01299447zbMath0821.90131MaRDI QIDQ1328431
Antonio Sassano, Carlo Mannino
Publication date: 26 July 1994
Published in: Computational Optimization and Applications (Search for Journal in Brave)
exact solutionbranch-and-boundgreedy algorithmmaximum cliquemaximum stable setmaximum cardinality stable set problem
Related Items (16)
An exact algorithm for the maximum stable set problem ⋮ Computational study of large-scale \(p\)-median problems ⋮ Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring ⋮ Solving a bicriteria problem of optimal service centers location ⋮ Polynomial size IP formulations of knapsack may require exponentially large coefficients ⋮ Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs ⋮ Strong lift-and-project cutting planes for the stable set problem ⋮ A computational study of a cutting plane algorithm for university course timetabling ⋮ Solving hard set covering problems ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ The generalized independent set problem: polyhedral analysis and solution approaches ⋮ A branch-and-cut algorithm for graph coloring ⋮ Block linear majorants in quadratic 0--1 optimization ⋮ A branch-and-cut algorithm for the maximum cardinality stable set problem ⋮ A fast algorithm for the maximum weight clique problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization of resource location in hierarchical computer networks
- Finding maximum cliques in arbitrary and in special graphs
- An exact algorithm for the maximum clique problem
- Relaxations of vertex packing
- A probabilistic heuristic for a computationally difficult set covering problem
- On maximal independent sets of vertices in claw-free graphs
- An interior point algorithm to solve computationally difficult set covering problems
- Test case generators and computational results for the maximum clique problem
- The maximum clique problem
- An exact algorithm for the maximum stable set problem
- Finding a Maximum Clique in an Arbitrary Graph
- A note on some computationally difficult set covering problems
- A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
- Efficient algorithms for interval graphs and circular-arc graphs
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- Algorithms on circular-arc graphs
- New methods to color the vertices of a graph
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- A branch and bound algorithm for the maximum clique problem
This page was built for publication: An exact algorithm for the maximum stable set problem
