On the analysis of independent sets via multilevel splitting
| Autor: | Dirk P. Kroese, Radislav Vaisman |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
021103 operations research
Computer Networks and Communications Computer science 0211 other engineering and technologies Graph theory 02 engineering and technology State (functional analysis) 01 natural sciences 010104 statistics & probability Counting problem Hardware and Architecture Independent set Complexity class 0101 mathematics Algorithm Software Information Systems |
| Zdroj: | Networks. 71:281-301 |
| ISSN: | 1097-0037 0028-3045 |
| DOI: | 10.1002/net.21805 |
| Popis: | Counting the number of independent sets is an important problem in graph theory, combinatorics, optimization, and social sciences. However, a polynomial-time exact calculation, or even a reasonably close approximation, is widely believed to be impossible, since their existence implies an efficient solution to various problems in the non-deterministic polynomial-time complexity class. To cope with the approximation challenge, we express the independent set counting problem as a rare-event estimation problem. We develop a multilevel splitting algorithm which is generally capable of delivering accurate results, while using a manageable computational effort, even when applied to large graphs. We apply the algorithm to both counting and optimization (finding a maximum independent set) problems, and show that it compares favorably with the existing state of the art. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text