6533b7d9fe1ef96bd126c430
RESEARCH PRODUCT
REDUCTION OF CONSTRAINT SYSTEMS
Samy Ait-aoudia Roland Jegou Dominique Micheluccisubject
FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)bipartite graphsmatchingperfect matching[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]maximum matching[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]geometric modelingComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATIONFOS: Mathematics[ INFO.INFO-CG ] Computer Science [cs]/Computational Geometry [cs.CG]Mathematics - CombinatoricsCombinatorics (math.CO)constraintsComputer Science - Discrete Mathematicsdescription
Geometric modeling by constraints leads to large systems of algebraic equations. This paper studies bipartite graphs underlaid by systems of equations. It shows how these graphs make possible to polynomially decompose these systems into well constrained, over-, and underconstrained subsystems. This paper also gives an efficient method to decompose well constrained systems into irreducible ones. These decompositions greatly speed up the resolution in case of reducible systems. They also allow debugging systems of constraints.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1993-12-06 |