An exact algorithm for the maximum probabilistic clique problem

DOI10.1007/s10878-013-9699-4zbMath1302.90187OpenAlexW2120286774MaRDI QIDQ405671

Eduardo L. Pasiliao, Zhuqi Miao, Balabhaskar Balasundaram

Publication date: 5 September 2014

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9699-4

zbMATH Keywords

branch-and-boundmaximum clique problemprobabilistic programmingprobabilistic clique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (3)

Detecting robust cliques in graphs subject to uncertain edge failures ⋮ New restrictions on defective coloring with applications to Steinberg-type graphs ⋮ On risk-averse maximum weighted subgraph problems

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• Sample average approximation method for chance constrained programming: Theory and applications
• An algorithm for finding a maximum clique in a graph
• The maximum clique problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• A fast algorithm for the maximum clique problem
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
• Improvements to MCS algorithm for the maximum clique problem
• Clique-detection models in computational biochemistry and genomics
• Convexity and decomposition of mean-risk stochastic programs
• Clique Relaxation Models in Social Network Analysis
• Theory and Applications of Robust Optimization
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• An Integer Programming and Decomposition Approach to General Chance-Constrained Mathematical Programs
• A Sample Approximation Approach for Optimization with Probabilistic Constraints
• Lectures on Stochastic Programming
• A Best Possible Heuristic for the k-Center Problem
• Finding a Maximum Clique in an Arbitrary Graph
• Graph Colorings
• Node-and edge-deletion NP-complete problems
• Convex Approximations of Chance Constrained Programs

This page was built for publication: An exact algorithm for the maximum probabilistic clique problem