EBSCO Logo
Connecting you to content on EBSCOhost
Results
Title

On Extracting Maximum Stable Sets in Perfect Graphs Using Lovász's Theta Function.

Authors

Yildirim, E. Alper; Fan-Orzechowski, Xiaofei

Abstract

We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lovász's theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its induced subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable set in a perfect graph using the theta function. Our algorithm iteratively transforms an approximate solution of the semidefinite formulation of the theta function into an approximate solution of another formulation, which is then used to identify a vertex that belongs to a maximum stable set. The subgraph induced by that vertex and its neighbors is removed and the same procedure is repeated on successively smaller graphs. We establish that solving the theta problem up to an adaptively chosen, fairly rough accuracy suffices in order for the algorithm to work properly. Furthermore, our algorithm successfully employs a warm-start strategy to recompute the theta function on smaller subgraphs. Computational results demonstrate that our algorithm can efficiently extract maximum stable sets incomparable time it takes to solve the theta problem on the original graph to optimality.

Subjects

THETA functions; PERFECT graphs; GRAPH theory; GRAPHIC methods; GRAPH algorithms; MATHEMATICAL optimization; MATHEMATICAL analysis; MATHEMATICAL programming; NUMERICAL analysis

Publication

Computational Optimization & Applications, 2006, Vol 33, Issue 2/3, p229

ISSN

0926-6003

Publication type

Academic Journal

DOI

10.1007/s10589-005-3060-5

EBSCO Connect | Privacy policy | Terms of use | Copyright | Manage my cookies
Journals | Subjects | Sitemap
© 2025 EBSCO Industries, Inc. All rights reserved