Parameterized Complexity Results in Symmetry Breaking

DOI10.1007/978-3-642-17493-3_3zbMath1309.68104arXiv1009.1174MaRDI QIDQ3058684

Toby Walsh

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.1174

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

Related Items

Variable symmetry breaking in numerical constraint problems, Constraint-directed search for all-interval series

Uses Software

• CSPLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Filtering algorithms for the NValue constraint
• Tree clustering for constraint networks
• Characterising tractable constraints
• The complexity of resolution with generalized symmetry rules
• Tractable cases of the extended global cardinality constraint
• Propagation algorithms for lexicographic ordering constraints
• Breaking Symmetry of Interchangeable Variables and Values
• Breaking All Value Symmetries in Surjection Problems
• General Symmetry Breaking Constraints
• A Sufficient Condition for Backtrack-Free Search
• Combining Symmetry Breaking and Global Constraints
• Filtering Algorithms for the NValue Constraint
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004