Symmetry-Breaking Constraints for Directed Graphs

ECAI 2024 : 27th European Conference on Artificial Intelligence, 19–24 October 2024, Santiago de Compostela, Spain – Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024), pp. 4248-4253, Frontiers in Artificial Intelligence and Applications ; Volume 392

Abstract

Finding a graph with given properties occurs as a sub-problem of many important problems in A.I. and other areas of computer science. Main approaches to solving such problems include automated reasoning and constraint satisfaction methods. These can often be substantially sped up by considering only a subset of graphs for each equivalence class of isomorphic graphs, motivating the use of symmetry-breaking constraints for graphs. We present a symmetry-breaking constraint for directed graphs, generalizing earlier works that have presented such constraints for undirected graphs without loops, and experimentally demonstrate their effectiveness.

Citation

Rintanen, J & Feyzbakhsh Rankooh, M 2024, Symmetry-Breaking Constraints for Directed Graphs. in ECAI 2024 : 27th European Conference on Artificial Intelligence, 19–24 October 2024, Santiago de Compostela, Spain – Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024). Frontiers in Artificial Intelligence and Applications, vol. 392, IOS Press, pp. 4248-4253, European Conference on Artificial Intelligence, Santiago de Compostela, Spain, 19/10/2024. < https://ebooks.iospress.nl/volumearticle/70093 >

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202412177876

Collections

[article-cris] Perustieteiden korkeakoulu / SCI

Show all metadata

Symmetry-Breaking Constraints for Directed Graphs

Access rights

URL

Journal Title

Journal ISSN

Volume Title

Authors

Date

Department

Major/Subject

Mcode

Degree programme

Language

Pages

Series

Abstract

Description

Keywords

Other note

Citation

Permanent link to this item

Collections