Dulmage-Mendelsohn Canonical Decomposition as a generic pruning technique

1. Alt, H., Blum, N., Mehlhorn, K., & Paul, M. (1991). Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1.5} \sqrt {m / \log n})\). Information Processing Letters, 37, 237–240.

   Article  MathSciNet  MATH  Google Scholar 

2. Beldiceanu, N., Carlsson, M., & Rampon, J.-X. (2006). Global constraint catalog. Technical Report T2005-08, Swedish Institute of Computer Science, 15 Sept 2006.

3. Beldiceanu, N., Katriel, I., & Thiel, S. (2004). Filtering algorithms for the SAME constraint. Lecture Notes in Computer Science, 3011, 65–79.

   Article  Google Scholar 

4. Berge, C. (1957). Two theorems in graph theory. Proceedings of the National Academy of Sciences of the United States of America, 43, 842–844.

   Article  MathSciNet  MATH  Google Scholar 

5. Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2001). Introduction to algorithms (2nd ed.). Cambridge, MA: MIT Press/McGraw-Hill.

   MATH  Google Scholar 

6. Dulmage, A.L., & Mendelsohn, N.S. (1958). Coverings of bipartite graphs. Canadian Journal of Mathematics, 10, 517–534.

   Article  MathSciNet  MATH  Google Scholar 

7. Gabow, H.N., & Tarjan, R.E. (1985). A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30, 209–221.

   Article  MathSciNet  MATH  Google Scholar 

8. Hall, P. (1935). On representatives of subsets. Journal of the London Mathematical Society, 10, 26–30.

   Article  Google Scholar 

9. Hell, P., & Kirkpatrick, D. G. (1993). Algorithms for degree constrained graph factors of minimum deficiency. Journal of Algorithms, 14, 115–138.

   Article  MathSciNet  MATH  Google Scholar 

10. Hopcroft, J. E., & Karp, R. M. (1973). An O(n ^5/2) algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4), 225–231.

    Article  MathSciNet  MATH  Google Scholar 

11. Kocjan, W., & Kreuger, P. (2004). Filtering methods for symmetric cardinality constraint. Lecture Notes in Computer Science, 3011, 200–208.

    Article  Google Scholar 

12. König, D. (1916). Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen, 77, 453–465.

    Article  MathSciNet  MATH  Google Scholar 

13. Lovász, L., & Plummer, M. D. (1986). Matching theory. Annals of discrete mathematics (29). North-Holland, Amsterdam.

14. Norman, R. Z., & Rabin, M. O. (1959). An algorithm for a minimum cover of a graph. Proceedings of the American Mathematics Society, 10, 315–319.

    Article  MathSciNet  MATH  Google Scholar 

15. Older, W. J., Swinkels, G. M., & van Emden, M. H. (1995). Getting to the real problem: Experience with BNR Prolog in OR. In 3rd international conference on the Practical Application of Prolog (PAP’95) (pp. 465–478). Alinmead Software Ltd.

16. Petersen, J. (1891). Die Theorie der regulären Graphen. Acta Mathematica, 15, 193–220.

    Article  MathSciNet  MATH  Google Scholar 

17. Petit, T., Régin, J.-C., & Bessière, C. (2001). Specific filtering algorithms for over-constrained problems. Lecture Notes in Computer Science, 2239, 451–463.

    Article  Google Scholar 

18. Quimper, C.-G., López-Ortiz, A., van Beek, P., & Golynski, A. (2004). Improved algorithms for the global cardinality constraint. Lecture Notes in Computer Science, 3258, 542–556.

    Article  Google Scholar 

19. Régin, J.-C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proceedings of the 12th national conference on Artificial Intelligence (AAAI-94) (pp. 362–367).

20. Régin, J.-C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings of the 13th national conference on Artificial Intelligence (AAAI-96) (pp. 209–215).

21. Tarjan, R. E. (1972). Depth first search and linear graph algorithms. SIAM Journal on Computing, 1, 146–160.

    Article  MathSciNet  MATH  Google Scholar 

22. van Hentenryck, P., & Carillon, J.-P. (1988). Generality versus specificity: An experience with AI and OR techniques. In Proceedings of the National Conference on Artificial Intelligence (AAAI) (pp. 660–664).

23. Zanarini, A., Milano, M., & Pesant, G. (2006). Improved algorithm for the soft global cardinality constraint. Lecture Notes in Computer Science, 3990, 288–299.

    Article  Google Scholar 

24. Zhou, J. (1997). A permutation-based approach for solving the job-shop problem. Constraints, 2(2), 185–213.

    Article  MathSciNet  MATH  Google Scholar 

Download references