Standard
Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems. / Gocht, Stephan; McBride, Ross; McCreesh, Ciaran; Nordström, Jakob; Prosser, Patrick; Trimble, James.
Principles and Practice of Constraint Programming: 26th International Conference, CP 2020, Proceedings. ed. / Helmut Simonis. Springer, 2020. p. 338-357 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12333 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Gocht, S, McBride, R, McCreesh, C
, Nordström, J, Prosser, P & Trimble, J 2020,
Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems. in H Simonis (ed.),
Principles and Practice of Constraint Programming: 26th International Conference, CP 2020, Proceedings. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12333 LNCS, pp. 338-357, 26th International Conference on Principles and Practice of Constraint Programming, CP 2020, Louvain-la-Neuve, Belgium,
07/09/2020.
https://doi.org/10.1007/978-3-030-58475-7_20APA
Gocht, S., McBride, R., McCreesh, C.
, Nordström, J., Prosser, P., & Trimble, J. (2020).
Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems. In H. Simonis (Ed.),
Principles and Practice of Constraint Programming: 26th International Conference, CP 2020, Proceedings (pp. 338-357). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 12333 LNCS
https://doi.org/10.1007/978-3-030-58475-7_20Vancouver
Gocht S, McBride R, McCreesh C
, Nordström J, Prosser P, Trimble J.
Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems. In Simonis H, editor, Principles and Practice of Constraint Programming: 26th International Conference, CP 2020, Proceedings. Springer. 2020. p. 338-357. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12333 LNCS).
https://doi.org/10.1007/978-3-030-58475-7_20Author
Gocht, Stephan ; McBride, Ross ; McCreesh, Ciaran ; Nordström, Jakob ; Prosser, Patrick ; Trimble, James. / Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems. Principles and Practice of Constraint Programming: 26th International Conference, CP 2020, Proceedings. editor / Helmut Simonis. Springer, 2020. pp. 338-357 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12333 LNCS).
Bibtex
@inproceedings{6f0f178512e1407d821c0aa92d959627,
title = "Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems",
abstract = "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.",
author = "Stephan Gocht and Ross McBride and Ciaran McCreesh and Jakob Nordstr{\"o}m and Patrick Prosser and James Trimble",
year = "2020",
doi = "10.1007/978-3-030-58475-7_20",
language = "English",
isbn = "9783030584740",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "338--357",
editor = "Helmut Simonis",
booktitle = "Principles and Practice of Constraint Programming",
address = "Switzerland",
note = "26th International Conference on Principles and Practice of Constraint Programming, CP 2020 ; Conference date: 07-09-2020 Through 11-09-2020",
}
RIS
TY - GEN
T1 - Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems
AU - Gocht, Stephan
AU - McBride, Ross
AU - McCreesh, Ciaran
AU - Nordström, Jakob
AU - Prosser, Patrick
AU - Trimble, James
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-030-58475-7_20
DO - 10.1007/978-3-030-58475-7_20
M3 - Article in proceedings
AN - SCOPUS:85091288907
SN - 9783030584740
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 338
EP - 357
BT - Principles and Practice of Constraint Programming
A2 - Simonis, Helmut
PB - Springer
T2 - 26th International Conference on Principles and Practice of Constraint Programming, CP 2020
Y2 - 7 September 2020 through 11 September 2020
ER -
