A Branch and Bound Algorithm for the Stability Number of a Sparse Graph

References

• Arora S. , Safra S. Probabilistic Checking of Proofs: A New Characterization of Np. Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (1992) (IEEE Computer Society Press, Los Alamitos, CA) 2 13 Crossref, Google Scholar
• Babel L. Finding Maximum Cliques in Arbitrary and in Special Graphs. Computing (1991) 46 321 341 Crossref, Google Scholar
• Babel L. , Tinhofer G. A Branch and Bound Algorithm for the Maximum Clique Problem. ZOR-Methods and Models of Operations Research (1990) 34 207 217 Crossref, Google Scholar
• Balas E. , Yu C. S. Finding a Maximum Clique in an Arbitrary Graph. SIAM Journal on Computing (1986) 15 4 1054 1068 Crossref, Google Scholar
• Bourjolly J. M. , Gill P. , Laporte G. , Mercure H. , Johnson D. S. , Trick M. A. An Exact Quadratic 0–1 Algorithm for the Stable Set Problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 26: Cliques, Coloring, and Satisfiability (1996) (American Mathematical Society, Providence, RI) 53 73 Crossref, Google Scholar
• Bourjolly J.-M. , Pulleyblank W. R. König–Egerváry Graphs, 2-Bicritical Graphs and Fractional Matchings. Discrete Applied Mathematics (1989) 24 63 82 Crossref, Google Scholar
• Brélaz D. New Methods to Color the Vertices of a Graph. Communications of the ACM (1979) 22 251 256 Crossref, Google Scholar
• Brockington M. , Culberson J. C. , Johnson D. S. , Trick M. A. Camouflaging Independent Sets in Quasi-Random Graphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 26: Cliques, Coloring, and Satisfiability (1996) (American Mathematical Society, Providence, RI) 75 88 Crossref, Google Scholar
• Carraghan R. , Pardalos P. M. An Exact Algorithm for the Maximum Clique Problem. Operations Research Letters (1990) 9 375 382 Crossref, Google Scholar
• Deming R. W. Independence Numbers of Graphs—An Extension of the König–Egerváry Theorem. Discrete Mathematics (1979) 27 23 33 Crossref, Google Scholar
• Feige U. , Goldwasser S. , LováSz L. , Safra S. , Szegedy M. Approximating Clique is Almost Np-Complete. Proceedings of the 32rd IEEE Symposium on Foundations Computer Science (1991) (IEEE Computer Society Press, Los Alamitos, CA) 2 12 Crossref, Google Scholar
• Friden C. , Hertz A. , de Werra D. STABULUS: A Technique For Finding Stable Sets in Large Graphs with Tabu Search. Computing (1989) 42 35 44 Crossref, Google Scholar
• Friden C. , Hertz A. , de Werra D. TABARIS: An Exact Algorithm Based on Tabu Search for Finding a Maximum Independent Set in a Graph. Computers and Operations Research (1990) 17 5 437 445 Crossref, Google Scholar
• Fulkerson D. R. , Nemhauser G. L. , Trotter L. E. Two Computationally Difficult Set Covering Problems that Arise in Computing the 1-Width of Incidence Matrices of Steiner Triple Systems. Mathematical Programming Study (1974) 2 72 81 Crossref, Google Scholar
• Gallai T. Über Extreme Punkt- und Kantenmengen. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominantae Sectio Mathematica (1959) 2 133 138 Google Scholar
• Gendreau M. , Soriano P. , Salvail L. Solving the Maximum Clique Problem Using a Tabu Search Approach. Annals Operations Research (1993) 41 385 403 Crossref, Google Scholar
• Grimmett G. R. , Pulleyblank W. R. Random Near-Regular Graphs and the Node Packing Problem. Operations Research Letters (1985) 4 169 174 Crossref, Google Scholar
• Hammer P. L. , Hansen P. , Simeone B. Vertices Belonging to All or to No Maximum Stable Sets of a Graph. SIAM Journal on Algebraic and Discrete Methods (1982) 3 4 511 522 Crossref, Google Scholar
• Johnson D. S. , Aragon C. R. , Mcgeoch L. A. , Schevon C. Optimization by Simulated Annealing: An Experimental Evaluation. Part II, Graph Coloring and Number Partitioning. Operations Research (1991) 39 3 378 406 Link, Google Scholar
• Mannino C. , Sassano A. An Exact Algorithm for the Maximum Stable Set Problem. Journal of Combinatorial Optimization Applications (1994) 3 243 258 Crossref, Google Scholar
• Nemhauser G. L. , Sigismondi G. A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing. Journal of the Operational Research Society (1992) 43 5 443 457 Crossref, Google Scholar
• Nemhauser G. L. , Trotter L. E. Properties of Vertex Packing and Independence System Polyhedra. Mathematical Programming (1974) 6 48 61 Crossref, Google Scholar
• Nemhauser G. L. , Trotter L. E. Vertex packings: Structural properties and algorithms. Mathematical Programming (1975) 8 232 248 Crossref, Google Scholar
• Padberg M. W. On the Facial Structure of Set Packing Polyhedra. Mathematical Programming (1973) 5 199 215 Crossref, Google Scholar
• Pardalos P. M. , Rodgers G. P. A Branch and Bound Algorithm for the Maximum Clique Problem. Computers and Operations Research (1992) 19 363 375 Crossref, Google Scholar
• Sanchis L. A. , Jagota A. Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem. INFORMS Journal on Computing (1996) 8 2 87 102 Link, Google Scholar
• Sterboul F. A Characterization of the Graphs in Which the Transversal Number Equals the Matching Number. Journal of Combinatorial Theory, Series B (1979) 27 228 229 Crossref, Google Scholar
• Welsh D. J. A. , Powell M. B. An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problem. Computer Journal (1967) 10 85 86 Crossref, Google Scholar
• Xue J. Fast Algorithms for Vertex Packing and Related Problems. (1991) . Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA Google Scholar