Around the Constructive Orbit Problem in Distributed Constraint Programming
スポンサーリンク
概要
- 論文の詳細を見る
This paper presents an efficient method to list equivalence classes (or orbits) of assignations of values to variables, where assignations are symmetrical through a group of variables and values permutations. We also present an algorithm designed to compute efficiently a canonical form of any assignation with respect to those orbits - problem also known as the constructive orbit problem. We illustrate how efficient our algorithm is and how it can significantly improve the resolution of symmetrical problems with DPOP, an efficient class of algorithms solving distributed constraint programming problems.
- 2011-02-28
著者
-
Nagamochi Hiroshi
Kyoto Univ.
-
Hiroshi Nakashima
ACCMS, Kyoto University
-
Xavier Olive
Kyoto University
-
Hiroshi Nakashima
Kyoto University
関連論文
- Constant Time Generation of Trees with Degree Bounds
- A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
- Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
- Enumerating Colored and Rooted Outerplanar Graphs
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems
- Orthogonal Drawings for Plane Graphs with Specified Face Areas
- Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
- Symmetry Breaking by Dominance Detection in Distributed Environments
- Around the Constructive Orbit Problem in Distributed Constraint Programming
- The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(Network Design, Control and Optimization)
- Accelerating A* algorithms by sweeping out small-degree nodes
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
- Multilingualization Based on RPC for Job-level Parallel Script Language, Xcrypt
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS