Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Indsendt manuskript, 339 KB, PDF-dokument
An algorithm is said to be certifying if it outputs, together with a solution to the problem it solves, a proof that this solution is correct. We explain how state of the art maximum clique, maximum weighted clique, maximal clique enumeration and maximum common (connected) induced subgraph algorithms can be turned into certifying solvers by using pseudo-Boolean models and cutting planes proofs, and demonstrate that this approach can also handle reductions between problems. The generality of our results suggests that this method is ready for widespread adoption in solvers for combinatorial graph problems.
Originalsprog | Engelsk |
---|---|
Titel | Principles and Practice of Constraint Programming : 26th International Conference, CP 2020, Proceedings |
Redaktører | Helmut Simonis |
Forlag | Springer |
Publikationsdato | 2020 |
Sider | 338-357 |
ISBN (Trykt) | 9783030584740 |
DOI | |
Status | Udgivet - 2020 |
Begivenhed | 26th International Conference on Principles and Practice of Constraint Programming, CP 2020 - Louvain-la-Neuve, Belgien Varighed: 7 sep. 2020 → 11 sep. 2020 |
Konference
Konference | 26th International Conference on Principles and Practice of Constraint Programming, CP 2020 |
---|---|
Land | Belgien |
By | Louvain-la-Neuve |
Periode | 07/09/2020 → 11/09/2020 |
Navn | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Vol/bind | 12333 LNCS |
ISSN | 0302-9743 |
ID: 251866968