{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:30Z","timestamp":1760202750420},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>Different optimization problems defined on graphs find application in complex network analysis. Existing propositional encodings render impractical the use of propositional satisfiability (SAT) and maximum satisfiability (MaxSAT) solvers for solving a variety of these problems on large graphs. This paper has two main contributions. First, the paper identifies sources of inefficiency in existing encodings for different optimization problems in graphs. Second, for the concrete case of the maximum clique problem, the paper develops a novel encoding which is shown to be far more compact than existing encodings for large sparse graphs. More importantly, the experimental results show that the proposed encoding enables existing SAT solvers to compute a maximum clique for large sparse networks, often more efficiently than the state of the art.<\/jats:p>","DOI":"10.24963\/ijcai.2017\/91","type":"proceedings-article","created":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T09:14:07Z","timestamp":1501233247000},"page":"652-658","source":"Crossref","is-referenced-by-count":2,"title":["Cardinality Encodings for Graph Optimization Problems"],"prefix":"10.24963","author":[{"given":"Alexey","family":"Ignatiev","sequence":"first","affiliation":[{"name":"LASIGE, Faculdade de Ci\u00eancias, Universidade de Lisboa, Portugal"},{"name":"ISDCT SB RAS, Irkutsk, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio","family":"Morgado","sequence":"additional","affiliation":[{"name":"LASIGE, Faculdade de Ci\u00eancias, Universidade de Lisboa, Portugal"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joao","family":"Marques-Silva","sequence":"additional","affiliation":[{"name":"LASIGE, Faculdade de Ci\u00eancias, Universidade de Lisboa, Portugal"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"26","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)","University of Technology Sydney (UTS)","Australian Computer Society (ACS)"],"acronym":"IJCAI-2017","name":"Twenty-Sixth International Joint Conference on Artificial Intelligence","start":{"date-parts":[[2017,8,19]]},"theme":"Artificial Intelligence","location":"Melbourne, Australia","end":{"date-parts":[[2017,8,26]]}},"container-title":["Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T11:52:12Z","timestamp":1501242732000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2017\/91"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2017\/91","relation":{},"subject":[],"published":{"date-parts":[[2017,8]]}}}