Constraints for symmetry breaking in graph representation
Constraints for symmetry breaking in graph representation
复制标题
图表示中对称性破缺的约束
DOI：
10.1007/s10601-018-9294-5
复制
发表时间：
2018
期刊：
影响因子：
1.6
通讯作者：
Codish M
中科院分区：
文献类型：
--
作者：
Codish M
许多复杂的组合问题产生于一系列的科学应用（如计算机网络，数学化学和生物信息学），涉及到寻找一个满足给定性质的无向图。由于对于任何可能的解决方案，可以有大量的同构表示，这些问题可以很快变得棘手。缓解这个问题的一种方法是通过在搜索过程中打破对称来消除尽可能多的同构副本-即通过引入约束，确保为每个等价类生成至少一个代表图，而不是整个类。目标是生成尽可能少的每个类的成员-理想情况下正好是一个：在这种情况下，对称性破缺被称为重复。在本文中，我们介绍了新的，有效的和紧凑的，对称性破缺无向图搜索的限制。虽然不完整，但这些证明在修剪图的搜索方面非常有益。我们举例说明了对称破缺在图表示中的应用，以解决极值图论中的几个开放实例。我们还说明了我们的方法的应用程序，表现出额外的对称性，由于在任何解决方案的边缘的颜色可以置换的事实，图的边缘着色问题。
Many complex combinatorial problems arising from a range of scientific applications (such as computer networks, mathematical chemistry and bioinformatics) involve searching for an undirected graph satisfying a given property. Since for any possible solution there can be a large number of isomorphic representations, these problems can quickly become intractable. One way to mitigate this problem is to eliminate as many isomorphic copies as possible bybreakingsymmetry during search - i.e. by introducing constraints that ensure that at least one representative graph is generated for each equivalence class, but not the entire class. The goal is to generate as few members of each class as possible - ideally exactly one: the symmetry break is said to becompletein this case. In this paper we introduce novel, effective and compact, symmetry breaking constraints for undirected graph search. While incomplete, these prove highly beneficial in pruning the search for a graph. We illustrate the application of symmetry breaking in graph representation to resolve several open instances in extremal graph theory. We also illustrate the application of our approach to graph edge coloring problems which exhibit additional symmetries due to the fact that the colors of the edges in any solution can be permuted.
登录
查看更多内容
DOI：
10.1016/s0012-365x(00)00265-x
发表时间：
2001
期刊：
Discret. Math.
影响因子：
--
作者：
Ping Wang;G. Dueck;S. MacMillan
通讯作者：
S. MacMillan
DOI：
10.1016/j.dam.2005.10.018
发表时间：
2001
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
I. Shlyakhter
通讯作者：
I. Shlyakhter
DOI：
--
发表时间：
1993
期刊：
International Syposium on Methodologies for Intelligent Systems
影响因子：
--
作者：
J. Puget
通讯作者：
J. Puget
用于优化 SAT 编码的布尔等传播
DOI：
10.1007/978-3-642-23786-7_47
发表时间：
2011
期刊：
arXiv: Combinatorics
影响因子：
--
作者：
Amit Metodi;M. Codish;Vitaly Lagoon;Peter James Stuckey
通讯作者：
Peter James Stuckey
使用抽象和对称性破缺计算拉姆齐数 R(4,3,3)
影响因子：
1.6
作者：
M. Codish;Michael Frank;Avraham Itzhakov;Alice Miller
通讯作者：
Alice Miller