Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: J Comb Optim

Search In Journal Title:

Abbravation: Journal of Combinatorial Optimization

Search In Journal Abbravation:

Publisher

Springer US

Search In Publisher:

DOI

10.1007/bf01936979

Search In DOI:

ISSN

1573-2886

Search In ISSN:
Search In Title Of Papers:

An exact algorithm for the maximum probabilistic c

Authors: Zhuqi Miao Balabhaskar Balasundaram Eduardo L Pasiliao
Publish Date: 2014/01/05
Volume: 28, Issue: 1, Pages: 105-120
PDF Link

Abstract

The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graphbased data mining social and biological network analysis and a variety of other fields This article investigates the problem when the edges fail independently with known probabilities This leads to the maximum probabilistic clique problem which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least theta in 01 which is a userspecified probability threshold We show that the probabilistic clique property is hereditary and extend a wellknown exact combinatorial algorithm for the maximum clique problem to a samplingfree exact algorithm for the maximum probabilistic clique problem The performance of the algorithm is benchmarked on a testbed of DIMACS clique instances and on a randomly generated testbedThe computational experiments reported in this article were performed at the Oklahoma State University High Performance Computing Center OSUHPCC The authors are grateful to Dr Dana Brunson for her support in conducting these experiments at OSUHPCC The authors would also like to thank the referees for the comments that helped us improve the presentation of this paper This research was supported by the US Department of Energy Grant DESC0002051 the Oklahoma Transportation Center Equipment Grant OTCES10210 and by the AFRL Mathematical Modeling and Optimization Institute

Keywords:

References

.
Search In Abstract Of Papers:
Other Papers In This Journal:
  1. A Lagrangian bound for many-to-many assignment problems
  2. New bounds for the balloon popping problem
  3. A two-stage method for member selection of emergency medical service
  4. Budget-constrained minimum cost flows
  5. On the complexity of partitioning a graph into a few connected subgraphs
  6. Median problems with positive and negative weights on cycles and cacti
  7. The unconstrained binary quadratic programming problem: a survey
  8. Multiple L ( j ,1)-labeling of the triangular lattice
  9. A hybrid algorithm based on variable neighbourhood for the strip packing problem
  10. Penalty guided genetic search for redundancy optimization in multi-state series-parallel power system
  11. Evaluation performance of genetic algorithm and tabu search algorithm for solving the Max-RWA problem in all-optical networks
  12. Modified differential evolution with self-adaptive parameters method
  13. Extremal polyomino chains with respect to general Randić index
  14. The weighted link ring loading problem
  15. A new recombination lower bound and the minimum perfect phylogenetic forest problem
  16. Optimization of loss-balanced multicast in all-optical WDM networks
  17. Reconfiguration of dominating sets
  18. Approximate event detection over multi-modal sensing data
  19. Mobile facility location: combinatorial filtering via weighted occupancy
  20. Bounded information dissemination in multi-channel wireless networks
  21. Total coloring of planar graphs without adjacent short cycles
  22. Disjunctive total domination in graphs
  23. A quadratic lower bound for colourful simplicial depth
Search Result: