×

zbMATH — the first resource for mathematics

Gallai-Edmonds decomposition as a pruning technique. (English) Zbl 1339.90322
Summary: We introduce a generic propagation mechanism for constraint programming. The method is based on the results of matching theory which is a mature and well-studied subject of graph theory. A first benefit of our new pruning technique comes from the fact that it can be applied on several global constraints whose solution is representable by a matching in a particular graph. In this work we describe a filtering scheme for such a family based on the Gallai-Edmonds Structure Theorem. In a number of important cases our method achieves hyper-arc consistency in polynomial time.

MSC:
90C35 Programming involving graphs or networks
90C25 Convex programming
91B68 Matching models
05C85 Graph algorithms (graph-theoretic aspects)
Software:
LEDA; SCIL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Althaus E, Bockmayr A, Elf M, Kasper T, Jünger M, Mehlhorn K (2002) SCIL-symbolic constraints in integer linear programming. Lecture Notes Comput Sci 2461:75-87 · Zbl 1019.90515
[2] Apt KR (2003) Principles of constraint programming. Cambridge University Press, Cambridge · Zbl 1187.68132
[3] Beldiceanu N, Carlsson M, Rampon J-X (2012) Global constraint catalog. Technical Report T2012-03, Swedish Institute of Computer Science, October 4 · Zbl 0572.68058
[4] Beldiceanu N, Contejean E (1994) Introducing global constraints in CHIP. Math Comput Model 20(12): 97-123 · Zbl 0816.68048
[5] Beldiceanu N, Katriel I, Lorca X (2006) Undirected forest constraints. Lecture Notes Comput Sci 3990: 29-43 · Zbl 1177.90392
[6] Beldiceanu N, Petit T (2004) Cost evaluation of soft global constraints. Lecture Notes Comput Sci 3011: 80-95 · Zbl 1094.68638
[7] Beldiceanu N, Simonis H (2012) A model seeker. Description and detailed results. Update of Technical Report 4C-2012-01, Cork Constraint Computation Centre, University College Cork, 19 May 2012 (unpublished)
[8] Berge, C, Two theorems in graph theory, Proc Natl Acad Sci USA, 43, 842-844, (1957) · Zbl 0086.16202
[9] Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge, MA
[10] Cymer, R, Dulmage-mendelsohn canonical decomposition as a generic pruning technique, Constraints, 17, 234-272, (2012) · Zbl 1309.90116
[11] Dechter R (2003) Constraint processing. Morgan Kaufmann Publishers, USA · Zbl 1057.68114
[12] Edmonds, J, Paths, trees and flowers, Can J Math, 17, 449-467, (1965) · Zbl 0132.20903
[13] Gabow, HN, An efficient implementation of edmonds’ algorithm for maximum matching on graphs, J Assoc Comput Mach, 23, 221-234, (1976) · Zbl 0327.05121
[14] Gabow HN (1983) An efficient reduction technique for degree-constrained subgraph and bidirected network flow problem. In: Proceedings of the 15th annual ACM symposium on theory of computing, New York, pp 448-456
[15] Gabow HN (1990) Data structures for weighted matching and nearest common ancestors with linking. In: Proceedings of the 1st annual ACM-SIAM symposium on discrete algorithms, Philadephia, pp 434-443 · Zbl 0800.68617
[16] Gabow, HN; Tarjan, RE, A linear-time algorithm for a special case of disjoint set union, J Comput Syst Sci, 30, 209-221, (1985) · Zbl 0572.68058
[17] Gallai, T, Kritische graphen II, Magyar Tudományos Akadémia; Matematikai Kutató Intézetének Közleményei, 8, 373-395, (1963) · Zbl 0144.23204
[18] Gallai, T, Maximale systeme unabhängiger kanten, Magyar Tudományos Akadémia; Matematikai Kutató Intézetének Közleményei, 9, 401-413, (1964) · Zbl 0135.42001
[19] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco, CA
[20] Henz M, Müller T, Thiel S (2004) Global constraints for round robin tournament scheduling. Eur J Oper Res 1(153):92-101 · Zbl 1053.90037
[21] Lovász L. (1987) Matching structure and the matching lattice. J Comb Theory (B) 43:187-222 · Zbl 0659.05081
[22] Lovász L, Plummer MD (1986) Matching theory. Annals of discrete mathematics (29). North-Holland, Amsterdam
[23] Mehlhorn K, Näher S (1999) LEDA: a platform for combinatorial and geometric computing. Cambridge University Press, Cambridge · Zbl 0976.68156
[24] Meijer, H; Núñez-Rodríguez, Y; Rappaport, D, An algorithm for computing simple k-factors, Inf Process Lett, 109, 620-625, (2009) · Zbl 1209.68380
[25] Micali S, Vazirani VV (1980) An \(O(\sqrt{|V|}· |E|)\) algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st annual symposium on foundations of computer science, pp 17-27
[26] Norman RZ, Rabin MO (1959) An algorithm for a minimum cover of a graph. Proc Am Math Soc 10: 315-319 · Zbl 0093.37702
[27] Petersen J (1891) Die Theorie der regulären Graphen. Acta Math 15:193-220 · Zbl 0132.20903
[28] Petit T, Régin J-C, Bessière C (2001) Specific filtering algorithms for over-constrained problems. Lecture Notes Comput Sci 2239:451-463 · Zbl 1067.68663
[29] Régin J.C. (1999) The symmetric alldiff constraint. In: Proceedings of the 16th international joint conference on artificial intelligence (IJCAI-99), pp 420-425
[30] Régin J-C, Petit T, Bessiere C, Puget J-F (2000) An original constraint based approach for solving over constrained problems. Lecture Notes Comput Sci 1894:543-548 · Zbl 1044.68793
[31] Tarjan RE (1983) Data structures and network algorithms. SIAM Press, Philadelphia, PA
[32] Trick MA (2003) Integer and constraint programming approaches for round-robin tournament scheduling. Lecture Notes Comput Sci 2740:63-77
[33] Tsang E (1993) Foundations of constraint satisfaction. Academic Press, New York
[34] Tutte, WT, A short proof of the factor theorem for finite graphs, Can J Math, 6, 347-352, (1954) · Zbl 0055.17102
[35] Tutte, WT, Graph factors, Combinatorica, 1, 79-97, (1981) · Zbl 0494.05046
[36] van Hoeve W-J (2001) The alldifferent constraint: a survey. In: Proceedings of the 6th annual workshop of the ERCIM working group on constraints, Prague, Czech Republic · Zbl 0806.05058
[37] Vazirani, VV, A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{|V|}· |E|)\) general graph maximum matching algorithm, Combinatorica, 14, 71-109, (1994) · Zbl 0806.05058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.