An exact algorithm for the maximum stable set problem

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)

zbMATH Keywords

exact solutionbranch-and-boundgreedy algorithmmaximum cliquemaximum stable setmaximum cardinality stable set problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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