Exact Algorithms for Maximum Clique: A Computational Study

Autor: Patrick Prosser

Publikováno v: Algorithms, Vol 5, Iss 4, Pp 545-587 (2012)

We investigate a number of recently reported exact algorithms for the maximum clique problem. The program code is presented and analyzed to show how small changes in implementation can have a drastic effect on performance. The computational study dem

Externí odkaz: https://doaj.org/article/c63db3cf45b34c91910ee770af2af025

Finding subgraphs with side constraints

Autor: Patrick Prosser, Christopher Jefferson, Jessica Enright, Özgür Akgün, Steffen Zschaler, Ciaran McCreesh

Publikováno v: Integration of Constraint Programming, Artificial Intelligence, and Operations Research ISBN: 9783030782290
CPAIOR

Funding: This research was supported by the Engineering and Physical Sciences Research Council [grant number EP/P026842/1]. The subgraph isomorphism problem is to find a small “pattern” graph inside a larger “target” graph. There are excellen

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c3912c0276f6a206ac26e6106ab6c2fc
https://hdl.handle.net/10023/24216

Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems

Autor: Patrick Prosser, Ciaran McCreesh, James Trimble, Stephan Gocht, Jakob Nordström, Ross McBride

Publikováno v: Lecture Notes in Computer Science ISBN: 9783030584740
CP
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_20

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 max

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::02758b014059f549a17bd4d5253052e8
https://eprints.gla.ac.uk/221064/7/221064.pdf

Constraints for symmetry breaking in graph representation

Autor: Michael Codish, Peter J. Stuckey, Alice Miller, Patrick Prosser

Many complex combinatorial problems arising from a range of scientific\ud applications (such as computer networks, mathematical chemistry and\ud bioinformatics) involve searching for an undirected graph satisfying a given\ud property. Since for any p

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a4e0175893b58dfb343d8b88e35aa2f1
https://eprints.gla.ac.uk/165865/7/165865.pdf

A review of literature on parallel constraint solving

Autor: Ian P. Gent, Ciaran McCreesh, Chris Unsworth, Peter Nightingale, Ian Miguel, Neil C. A. Moore, Patrick Prosser

As multicore computing is now standard, it seems irresponsible for constraints researchers to ignore the implications of it. Researchers need to address a number of issues to exploit parallelism, such as: investigating which constraint algorithms are

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::60425ddbd6340d75262c960abea5250f
https://eprints.gla.ac.uk/171801/7/171801.pdf